Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with k-wise independent:
TR16-083 | 23rd May 2016
Nader Bshouty

Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets

Derandomization of Chernoff bound with union bound is already proven in many papers.
We here give another explicit version of it that obtains a construction of size
that is arbitrary close to the probabilistic nonconstructive size.

We apply this to give a new simple polynomial time constructions of
almost $k$-wise ... more >>>

ISSN 1433-8092 | Imprint