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 TR23-049 | 29th April 2024 22:09

Top-Down Lower Bounds for Depth-Four Circuits

RSS-Feed




Revision #1
Authors: Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Accepted on: 29th April 2024 22:09
Downloads: 108
Keywords: 


Abstract:

We present a top-down lower-bound method for depth-$4$ boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-$4$ circuits of size exponential in $n^{1/3}$. Our proof is an application of robust sunflowers and block unpredictability.



Changes to previous version:

Conference version


Paper:

TR23-049 | 17th April 2023 20:12

Top-Down Lower Bounds for Depth-Four Circuits





TR23-049
Authors: Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Publication: 19th April 2023 15:02
Downloads: 588
Keywords: 


Abstract:

We present a top-down lower-bound method for depth-$4$ boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-$4$ circuits of size exponential in $n^{1/3}$. Our proof is an application of robust sunflowers and block unpredictability.



ISSN 1433-8092 | Imprint