2026-07-20T05:13:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25399 2026-04-13T08:51:01Z ddc:004 open_access

Lower Bounds Beyond DNF of Parities Riazanov, Artur Sofronova, Anastasia Sokolov, Dmitry boolean circuits top-down unpredictability We consider a subclass of AC⁰[2] circuits that simultaneously captures DNF∘Xor and depth-3 AC⁰ circuits. For this class we show a technique for proving lower bounds inspired by the top-down approach. We give lower bounds for the middle slice function, inner product function, and affine dispersers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artur Riazanov and Anastasia Sofronova and Dmitry Sokolov 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.112 urn:nbn:de:0030-drops-253996 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.112 eng https://creativecommons.org/licenses/by/4.0/legalcode