2026-07-22T08:26:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16575 2024-03-06T10:57:50Z ddc:004 open_access

A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates Mihajlin, Ivan Sofronova, Anastasia formula complexity communication complexity Karchmer-Raz-Wigderson conjecture De Morgan formulas We prove that a modification of Andreev’s function is not computable by (3 + α - ε) log(n) depth De Morgan formula with (2α - ε)log{n} layers of AND gates at the top for any 0 < α < 1/5 and any constant ε > 0. In order to do this, we prove a weak variant of Karchmer-Raz-Wigderson conjecture. To be more precise, we prove the existence of two functions f : {0,1}ⁿ → {0,1} and g : {0,1}ⁿ → {0,1}ⁿ such that f(g(x) ⊕ y) is not computable by depth (1 + α - ε) n formulas with (2 α - ε) n layers of AND gates at the top. We do this by a top-down approach, which was only used before for depth-3 model. Our technical contribution includes combinatorial insights into structure of composition with random boolean function, which led us to introducing a notion of well-mixed sets. A set of functions is well-mixed if, when composed with a random function, it does not have subsets that agree on large fractions of inputs. We use probabilistic method to prove the existence of well-mixed sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivan Mihajlin and Anastasia Sofronova 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.13 urn:nbn:de:0030-drops-165755 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.13 eng https://creativecommons.org/licenses/by/4.0/legalcode