Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR25-024 | 8th September 2025 16:27

Lower Bounds Beyond DNF of Parities

RSS-Feed




Revision #1
Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Accepted on: 8th September 2025 16:27
Downloads: 30
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.



Changes to previous version:

Fixed a bug in the writing of Theorem 3.1


Paper:

TR25-024 | 9th March 2025 00:45

Lower Bounds Beyond DNF of Parities





TR25-024
Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Publication: 9th March 2025 09:29
Downloads: 736
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