DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.34

Lower Bounds on Same-Set Inner Product in Correlated Spaces

Authors: Jan Hazla, Thomas Holenstein, and Elchanan Mossel

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

Abstract

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.

Cite as

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

DOI: 10.4230/LIPIcs.STACS.2015.392

Upper Tail Estimates with Combinatorial Proofs

Authors: Jan Hazla and Thomas Holenstein

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

Abstract

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).

Cite as

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}
}

Search Results

Documents authored by Hazla, Jan

Lower Bounds on Same-Set Inner Product in Correlated Spaces

Abstract

Cite as

Upper Tail Estimates with Combinatorial Proofs

Abstract

Cite as

Thanks for your feedback!

Could not send message