# Building a “balanced” universal set

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:

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.

• 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 Feb 4 '14 at 19:21
• @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 Feb 4 '14 at 20:58
• @SashoNikolov is correct. When I first saw universal sets that was also my first thought, bit they're quite different. – R B Feb 4 '14 at 21:11
• 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 Feb 4 '14 at 21:35
• oh duh. sorry. got my quantifiers mixed up. – Suresh Venkat Feb 4 '14 at 22:25