2026-07-23T17:33:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13260 2024-03-06T10:51:58Z ddc:004 open_access

Size Bounds on Low Depth Circuits for Promise Majority Cook, Joshua AC0 Approximate Counting Approximate Majority Promise Majority Depth 3 Circuits Circuit Lower Bound We give two results on the size of AC0 circuits computing promise majority. ε-promise majority is majority promised that either at most an ε fraction of the input bits are 1 or at most ε are 0. - First, we show super-quadratic size lower bounds on both monotone and general depth-3 circuits for promise majority. - For any ε ∈ (0, 1/2), monotone depth-3 AC0 circuits for ε-promise majority have size Ω̃(ε³ n^{2 + (ln(1 - ε))/(ln(ε))}). - For any ε ∈ (0, 1/2), general depth-3 AC0 circuits for ε-promise majority have size Ω̃(ε³ n^{2 + (ln(1 - ε²))/(2ln(ε))}). These are the first quadratic size lower bounds for depth-3 ε-promise majority circuits for ε < 0.49. - Second, we give both uniform and non-uniform sub-quadratic size constant-depth circuits for promise majority. - For integer k ≥ 1 and constant ε ∈ (0, 1/2), there exists monotone non uniform AC0 circuits of depth-(2 + 2 k) computing ε-promise majority with size Õ(n^{1/(1 - 2^{-k})}). - For integer k ≥ 1 and constant ε ∈ (0, 1/2), there exists monotone uniform AC0 circuit of depth-(2 + 2 k) computing ε-promise majority with size n^{1/(1 - (2/3) ^k) + o(1)}. These circuits are based on incremental improvements to existing depth-3 circuits for promise majority given by Ajtai [Miklós Ajtai, 1983] and Viola [Emanuele Viola, 2009] combined with a divide and conquer strategy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Cook 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.19 urn:nbn:de:0030-drops-132609 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.19 eng https://creativecommons.org/licenses/by/3.0/legalcode