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 (NSS).
  2. Nearly optimal build of $\delta$-balanced perfect hashing family by Alon and Gunter.
  3. Simple Constructions of Almost k-wise Independent Random Variables (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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.