Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-024 | 9th March 2025 00:45

Lower Bounds Beyond DNF of Parities

RSS-Feed




TR25-024
Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Publication: 9th March 2025 09:29
Downloads: 163
Keywords: 


Abstract:

We consider a subclass of $\mathbf{AC}^0[2]$ circuits that simultaneously captures $\mathrm{DNF} \circ \mathrm{Xor}$ and depth-$3$ $\mathbf{AC}^0$ 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.



ISSN 1433-8092 | Imprint