2026-07-29T10:45:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10128 2024-03-06T10:45:27Z ddc:004 open_access

Cubic Formula Size Lower Bounds Based on Compositions with Majority Gál, Anna Tal, Avishay Trejo Nuñez, Adrian formula lower bounds random restrictions KRW conjecture composition 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Gál and Avishay Tal and Adrian Trejo Nuñez 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.35 urn:nbn:de:0030-drops-101283 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.35 eng https://creativecommons.org/licenses/by/3.0/legalcode