2026-07-23T15:19:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4929 2024-03-06T10:35:34Z ddc:004 open_access

Upper Tail Estimates with Combinatorial Proofs Hazla, Jan Holenstein, Thomas concentration bounds expander random walks polynomial concentration 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Hazla and Thomas Holenstein 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.392 urn:nbn:de:0030-drops-49291 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.392 eng https://creativecommons.org/licenses/by/3.0/legalcode