Document

**Published in:** LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Let P be a probability distribution over a finite alphabet Omega^L with all L marginals equal. Let X^(1), ..., X^(L), where X^(j) = (X_1^(j), ..., X_n^(j)) be random vectors such that for every coordinate i in [n] the tuples (X_i^(1), ..., X_i^(L)) are i.i.d. according to P.
The question we address is: does there exist a function c_P independent of n such that for every f: Omega^n -> [0, 1] with E[f(X^(1))] = m > 0 we have E[f(X^(1)) * ... * f(X^(n))] > c_P(m) > 0?
We settle the question for L=2 and when L>2 and P has bounded correlation smaller than 1.

Jan Hazla, Thomas Holenstein, and Elchanan Mossel. Lower Bounds on Same-Set Inner Product in Correlated Spaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hazla_et_al:LIPIcs.APPROX-RANDOM.2016.34, author = {Hazla, Jan and Holenstein, Thomas and Mossel, Elchanan}, title = {{Lower Bounds on Same-Set Inner Product in Correlated Spaces}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {34:1--34:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.34}, URN = {urn:nbn:de:0030-drops-66571}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.34}, annote = {Keywords: same set hitting, product spaces, correlation, lower bounds} }

Document

**Published in:** LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

We study generalisations of a simple, combinatorial proof of a Chernoff bound similar to the one by Impagliazzo and Kabanets (RANDOM, 2010).
In particular, we prove a randomized version of the hitting property of expander random walks and use it to obtain an optimal expander random
walk concentration bound settling a question asked by Impagliazzo and Kabanets.
Next, we obtain an upper tail bound for polynomials with input variables in [0, 1] which are not necessarily independent, but obey a certain condition inspired by Impagliazzo and Kabanets. The resulting bound
is applied by Holenstein and Sinha (FOCS, 2012) in the proof of a lower bound for the number of calls in a black-box construction of a pseudorandom generator from a one-way function.
We also show that the same technique yields the upper tail bound for the number of copies of a fixed graph in an Erdös–Rényi random graph,
matching the one given by Janson, Oleszkiewicz, and Rucinski (Israel J. Math, 2002).

Jan Hazla and Thomas Holenstein. Upper Tail Estimates with Combinatorial Proofs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 392-405, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hazla_et_al:LIPIcs.STACS.2015.392, author = {Hazla, Jan and Holenstein, Thomas}, title = {{Upper Tail Estimates with Combinatorial Proofs}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {392--405}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.392}, URN = {urn:nbn:de:0030-drops-49291}, doi = {10.4230/LIPIcs.STACS.2015.392}, annote = {Keywords: concentration bounds, expander random walks, polynomial concentration} }