Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-049 | 17th April 2023 20:12

Top-Down Lower Bounds for Depth-Four Circuits

RSS-Feed




TR23-049
Authors: Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Publication: 19th April 2023 15:02
Downloads: 463
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