Top-Down Lower Bounds for Depth-Four Circuits

2023/04/05 by Mika Göös, Göös, Mika, Artur Riazanov +5 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Low-power high-performance VLSI design #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2304.02555

openalex publication_date 2023/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity

Related

• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic\n circuits
• Arithmetic circuits: the chasm at depth four gets wider
• Circuit Depth Reductions
• Weights at the Bottom Matter When the Top is Heavy
• An average-case depth hierarchy theorem for Boolean circuits