Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.24
URN: urn:nbn:de:0030-drops-66475
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6647/
Boppana, Ravi ; Håstad, Johan ; Lee, Chin Ho ; Viola, Emanuele
Bounded Independence vs. Moduli
| pdf-format: |
|
Abstract
Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k <= 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.
BibTeX - Entry
@InProceedings{boppana_et_al:LIPIcs:2016:6647,
author = {Ravi Boppana and Johan Håstad and Chin Ho Lee and Emanuele Viola},
title = {{Bounded Independence vs. Moduli}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {24:1--24:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-018-7},
ISSN = {1868-8969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6647},
URN = {urn:nbn:de:0030-drops-66475},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.24},
annote = {Keywords: Bounded independence, Modulus}
}
| Keywords: | Bounded independence, Modulus | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 06.09.2016 |
