Constant-depth circuit size lower bounds

Summary of the project: Constant-depth logical circuits have been one of the most successful settings for complexity lower bounds. Early results established that the PARITY function (given an n bit string, are there an even number of 1?) does not have polynomial-size constant-depth circuits. Over a series of papers, we know that exponential-size constant-depth circuits are required to calculate PARITY, providing numerous new techniques and an almost-optimal lower bound using the powerful switching lemma or the satisfiability coding lemma. One of the aims of this project is to improve the already-known, sensitivity based, techniques and provide an essentially optimal lower bound for PARITY (or other highly sensitive functions). To find a new circuit switching technique based on the satisfiability coding lemma.
A similar, but much harder question, asks the minimum size of constant-depth circuits calculating the function MAJORITY (given an n bit string, are there more 1s than 0s?). There is a larger gap between the best-known constant-depth size bounds for MAJORITY. The sensitivity-based approaches coming from the analysis of PARITY are not powerful enough to provide tighter bounds for MAJORITY. Another aim of this project is to better understand the limitations of such techniques and to find alternative methods to attack the question regarding the complexity of MAJORITY. One candidate method is based on techniques in extremal hypergraph theory from combinatorics. The project aims to investigate the corresponding question, the generalized hypergraph Turán problem.
New lower bounds against constant-depth circuits often involve novel information about the structure of CNFs (which is essentially a depth 2 circuit). New structural results about CNFs historically translate to better CNF satisfiability (SAT) solvers. A successful project might be applied to improve or find new SAT solvers.

This project falls within the EPSRC Theoretical Computer Science research area, under ICT.