All Questions
Tagged with epsilon-nets co.combinatorics
4 questions
1
vote
0
answers
149
views
Hitting sets for sets of VC dimension d
Let $S$ be a collection of sets of binary vectors (in $\{0,1\}^m$) $S_1, S_2, \dotsc, S_t$ (say $t = O(m^d)$) each of VC dimension $d$. What can be said about the size of a hitting set $S_\text{hit}$ ...
- 11
4
votes
0
answers
266
views
Open problems on epsilon nets
What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?
- 41
11
votes
1
answer
1k
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
- 9,910
7
votes
2
answers
275
views
Counting Metrics
Say that I have a set of $n$ points $N$, and am interested in metrics $d:N\times N \rightarrow \mathbb{R}$ over $N$. Let $M$ denote the set of all metrics over $N$.
Now let me define the distance ...
- 9,910