3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$
    – Suresh Venkat
    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$
    – Sasho Nikolov
    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
    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$
    – Sasho Nikolov
    Feb 4, 2014 at 21:35
  • $\begingroup$ oh duh. sorry. got my quantifiers mixed up. $\endgroup$
    – Suresh Venkat
    Feb 4, 2014 at 22:25

0

Reset to default

Your Answer

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