Lune

FOCS2023Top-tier venue

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 n1/3n^{1 / 3}. 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.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

lune papers fulltext bbd5c8ff-2ae4-44d7-b147-41423b861c3b

Builds on2

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines