Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-083 | 23rd May 2016 09:44

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

RSS-Feed




TR16-083
Authors: Nader Bshouty
Publication: 25th May 2016 11:05
Downloads: 2097
Keywords: 


Abstract:

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 independent sets. We also give almost tight lower bounds
for the size of $k$-wise independent sets.



ISSN 1433-8092 | Imprint