4 Search Results for "Holenstein, Thomas"

Document
DOI: 10.4230/LIPIcs.CCC.2018.23
A Tight Lower Bound for Entropy Flattening

Authors: Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We study entropy flattening: Given a circuit C_X implicitly describing an n-bit source X (namely, X is the output of C_X on a uniform random input), construct another circuit C_Y describing a source Y such that (1) source Y is nearly flat (uniform on its support), and (2) the Shannon entropy of Y is monotonically related to that of X. The standard solution is to have C_Y evaluate C_X altogether Theta(n^2) times on independent inputs and concatenate the results (correctness follows from the asymptotic equipartition property). In this paper, we show that this is optimal among black-box constructions: Any circuit C_Y for entropy flattening that repeatedly queries C_X as an oracle requires Omega(n^2) queries. Entropy flattening is a component used in the constructions of pseudorandom generators and other cryptographic primitives from one-way functions [Johan Håstad et al., 1999; John Rompel, 1990; Thomas Holenstein, 2006; Iftach Haitner et al., 2006; Iftach Haitner et al., 2009; Iftach Haitner et al., 2013; Iftach Haitner et al., 2010; Salil P. Vadhan and Colin Jia Zheng, 2012]. It is also used in reductions between problems complete for statistical zero-knowledge [Tatsuaki Okamoto, 2000; Amit Sahai and Salil P. Vadhan, 1997; Oded Goldreich et al., 1999; Vadhan, 1999]. The Theta(n^2) query complexity is often the main efficiency bottleneck. Our lower bound can be viewed as a step towards proving that the current best construction of pseudorandom generator from arbitrary one-way functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.
Cite as

Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang. A Tight Lower Bound for Entropy Flattening. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CCC.2018.23,
  author =	{Chen, Yi-Hsiu and G\"{o}\"{o}s, Mika and Vadhan, Salil P. and Zhang, Jiapeng},
  title =	{{A Tight Lower Bound for Entropy Flattening}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{23:1--23:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.23},
  URN =		{urn:nbn:de:0030-drops-88669},
  doi =		{10.4230/LIPIcs.CCC.2018.23},
  annote =	{Keywords: Entropy, One-way function}
}
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-dev.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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.643
Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power

Authors: Chandan Dubey and Thomas Holenstein

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

Abstract
Let p be a prime and k, t be positive integers. Given a quadratic equation Q(x1,x2,...,xn)=t mod p^k in n-variables; we present a polynomial time Las-Vegas algorithm that samples a uniformly random solution of the quadratic equation.
Cite as

Chandan Dubey and Thomas Holenstein. Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 643-653, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dubey_et_al:LIPIcs.APPROX-RANDOM.2014.643,
  author =	{Dubey, Chandan and Holenstein, Thomas},
  title =	{{Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{643--653},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.643},
  URN =		{urn:nbn:de:0030-drops-47289},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.643},
  annote =	{Keywords: Quadratic Forms, Lattices, Modular, p-adic}
}
  • Refine by Author
  • 3 Holenstein, Thomas
  • 2 Hazla, Jan
  • 1 Chen, Yi-Hsiu
  • 1 Dubey, Chandan
  • 1 Göös, Mika
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 1 Entropy
  • 1 Lattices
  • 1 Modular
  • 1 One-way function
  • 1 Quadratic Forms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2014
  • 1 2015
  • 1 2016
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact