DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2019.35

Cubic Formula Size Lower Bounds Based on Compositions with Majority

Authors: Anna Gál, Avishay Tal, and Adrian Trejo Nuñez

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract

We define new functions based on the Andreev function and prove that they require n^{3}/polylog(n) formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the majority function (or its negation) on the middle slices of the Boolean cube, as well as iterated compositions of such functions. As a consequence, we obtain n^{3}/polylog(n) lower bounds on the (non-monotone) formula size of an explicit monotone function by combining the monotone address function with the majority function.

Cite as

Anna Gál, Avishay Tal, and Adrian Trejo Nuñez. Cubic Formula Size Lower Bounds Based on Compositions with Majority. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.ITCS.2019.35,
  author =	{G\'{a}l, Anna and Tal, Avishay and Trejo Nu\~{n}ez, Adrian},
  title =	{{Cubic Formula Size Lower Bounds Based on Compositions with Majority}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.35},
  URN =		{urn:nbn:de:0030-drops-101283},
  doi =		{10.4230/LIPIcs.ITCS.2019.35},
  annote =	{Keywords: formula lower bounds, random restrictions, KRW conjecture, composition}
}

Search Results

Documents authored by Trejo Nuñez, Adrian

Cubic Formula Size Lower Bounds Based on Compositions with Majority

Abstract

Cite as

Thanks for your feedback!

Could not send message