Top-Down Lower Bounds for Depth-Four Circuits
Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2023Year
4Citations
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 . Our proof is an application of robust sunflowers and block unpredictability.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext bbd5c8ff-2ae4-44d7-b147-41423b861c3bBuilds on2
Related papers
- Monotone Circuit Complexity of MatchingBruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova et al.STOC 2026 · 7 citations
- Superquadratic Lower Bounds for Depth-2 Linear Threshold CircuitsLijie Chen, Avishay Tal, Yichuan WangSTOC 2026
- Improved Lower Bounds for QAC0Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John WrightSTOC 2026 · 4 citations
- 3.1n - o(n) circuit lower bounds for explicit functionsJiatu Li, Tianqi YangSTOC 2022 · 13 citations
- Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR TreesPooya Hatami, William M. Hoza, Avishay Tal, Roei TellSTOC 2023 · 2 citations
