1 Search Results for "Trejo Nu�ez, Adrian"

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-dev.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}
}
  • Refine by Author
  • 1 Gál, Anna
  • 1 Tal, Avishay
  • 1 Trejo Nuñez, Adrian

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

  • Refine by Keyword
  • 1 KRW conjecture
  • 1 composition
  • 1 formula lower bounds
  • 1 random restrictions

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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