Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.35
URN: urn:nbn:de:0030-drops-101283
URL: https://drops.dagstuhl.de/opus/volltexte/2018/10128/
Gál, Anna ; Tal, Avishay ; Trejo Nuñez, Adrian
Cubic Formula Size Lower Bounds Based on Compositions with Majority
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{gl_et_al:LIPIcs:2018:10128,
author = {Anna G{\'a}l and Avishay Tal and Adrian Trejo Nu{\~n}ez},
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 = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10128},
URN = {urn:nbn:de:0030-drops-101283},
doi = {10.4230/LIPIcs.ITCS.2019.35},
annote = {Keywords: formula lower bounds, random restrictions, KRW conjecture, composition}
}
| Keywords: | formula lower bounds, random restrictions, KRW conjecture, composition | |
| Seminar: | 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) | |
| Issue date: | 2018 | |
| Date of publication: | 08.01.2019 |
