<p>A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called <em>$(n,k)$-universal</em> if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, all $2^k$ vectors appear in $\mathcal{U}$'s vectors when restricted to $S$.</p>

<p>A $(n,k)$-universal set is said to be $(T,\alpha)$-balanced if for every vector $v$ of length k and every subset $S\subset [n], |S|=k$, the number of vectors in $\mathcal{U}$ which has $v$ in indices $S$ is at least $\frac{T}{\alpha}$ and at most $T\cdot \alpha$. The original definition of the universal set only ensures that there exists at least one such vector $u\in \mathcal{U}$.</p>

<p>Related works for similar structures are:</p>

<ol>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.5859&amp;rep=rep1&amp;type=pdf" rel="nofollow">Nearly optimal build of $(n,k)$-universal set</a> (NSS).</li>
<li><a href="http://www.tau.ac.il/~nogaa/PDFS/bhash3.pdf" rel="nofollow">Nearly optimal build of $\delta$-balanced perfect hashing family</a> by Alon and Gunter.</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.6442" rel="nofollow">Simple Constructions of Almost k-wise Independent Random Variables</a> (AGHP).</li>
</ol>

<p><strong>My question is: is it possible to deterministically build a <em>small</em> $(T,\alpha)$-balanced  universal set?</strong></p>

<p>(By small, I mean $O(2^{k+\text{polylog}(k,\alpha)}\cdot \text{poly}(n))$).</p>

<p>It doesn't seem hard to show (using the probabilistic method) that such set exist, but I'm interested in explicit build.</p>

CC BY-SA 3.0
2014-02-04T19:21:25.107Z
Isn't an $(n,k)$-universal set merely a range space with VC dimension at least $k$ ? the elements of the range space are the "dimensions" and the ranges are the bit vectors interpreted as characteristic vectors ?
Suresh Venkat
CC BY-SA 3.0
2014-02-04T20:58:50.157Z
@SureshVenkat VC dimension at least $k$ only implies that there exists some set $S$ of size $k$ which is shattered. Here the requirement is that every set of size $k$ is shattered.
Sasho Nikolov
CC BY-SA 3.0
2014-02-04T21:11:17.563Z
@SashoNikolov is correct. When I first saw universal sets that was also my first thought, bit they're quite different.
R B
CC BY-SA 3.0
2014-02-04T21:35:41.870Z
Why doesn't what you need follow from the AGHP results, by setting $\epsilon = \alpha 2^{-k}$ in their max-norm almost $k$-wise independence construction?
Sasho Nikolov
CC BY-SA 3.0
2014-02-04T22:25:07.100Z
oh duh. sorry. got my quantifiers mixed up.
Suresh Venkat
<ds.algorithms><co.combinatorics><expanders><extremal-combinatorics>
Building a "balanced" universal set
R B
# Building a "balanced" universal set

(Asked by: username_0 on 2014-02-04)

A set of length $n$ binary vectors $\mathcal{U}=\{u\_1,..,u\_r\}$ is called *$(n,k)$-universal* if for all $S\subset [n], |S|=k$, $|\mathcal{U}\_{|S}|=2^k$, i.e. for every subset of indices of size $k$, all $2^k$ vectors appear in $\mathcal{U}$'s vectors when restricted to $S$.

A $(n,k)$-universal set is said to be $(T,\alpha)$-balanced if for every vector $v$ of length k and every subset $S\subset [n], |S|=k$, the number of vectors in $\mathcal{U}$ which has $v$ in indices $S$ is at least $\frac{T}{\alpha}$ and at most $T\cdot \alpha$. The original definition of the universal set only ensures that there exists at least one such vector $u\in \mathcal{U}$.

Related works for similar structures are:

1. [Nearly optimal build of $(n,k)$-universal set](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.5859&rep=rep1&type=pdf) (NSS).
2. [Nearly optimal build of $\delta$-balanced perfect hashing family](http://www.tau.ac.il/~nogaa/PDFS/bhash3.pdf) by Alon and Gunter.
3. [Simple Constructions of Almost k-wise Independent Random Variables](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.6442) (AGHP).

**My question is: is it possible to deterministically build a *small* $(T,\alpha)$-balanced universal set?**

(By small, I mean $O(2^{k+\text{polylog}(k,\alpha)}\cdot \text{poly}(n))$).

It doesn't seem hard to show (using the probabilistic method) that such set exist, but I'm interested in explicit build.

**Tags:** ds.algorithms, co.combinatorics, expanders, extremal-combinatorics
> **Comments:**
> **username_1**: Isn't an $(n,k)$-universal set merely a range space with VC dimension at least $k$ ? the elements of the range space are the "dimensions" and the ranges are the bit vectors interpreted as characteristic vectors ?  
> **username_2**: @SureshVenkat VC dimension at least $k$ only implies that there exists some set $S$ of size $k$ which is shattered. Here the requirement is that every set of size $k$ is shattered.  
> **username_0**: @SashoNikolov is correct. When I first saw universal sets that was also my first thought, bit they're quite different.  
> **username_2**: Why doesn't what you need follow from the AGHP results, by setting $\epsilon = \alpha 2^{-k}$ in their max-norm almost $k$-wise independence construction?  
> **username_1**: oh duh. sorry. got my quantifiers mixed up.  

---

## 0 answers

