License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.22
URN: urn:nbn:de:0030-drops-90264
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9026/
Go to the corresponding LIPIcs Volume Portal

Bogdanov, Andrej

Small Bias Requires Large Formulas

pdf-format:
LIPIcs-ICALP-2018-22.pdf (0.4 MB)

Abstract

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on (1) the size of general Boolean formulas, (2) the size of De Morgan formulas, and (3) correlation against small De Morgan formulas apply to small-biased functions. As a consequence, any strongly explicit small-biased generator is subject to the best-known explicit formula lower bounds in all these models.
On the other hand, we give a construction of a small-biased function that is tight with respect to lower bound (1) for the relevant range of parameters. We interpret this construction as a natural-type barrier against substantially stronger lower bounds for general formulas.

BibTeX - Entry

@InProceedings{bogdanov:LIPIcs:2018:9026,
  author =	{Andrej Bogdanov},
  title =	{{Small Bias Requires Large Formulas}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{22:1--22:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9026},
  URN =		{urn:nbn:de:0030-drops-90264},
  doi =		{10.4230/LIPIcs.ICALP.2018.22},
  annote =	{Keywords: formula lower bounds, natural proofs, pseudorandomness}
}

Keywords: formula lower bounds, natural proofs, pseudorandomness
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI