CS Colloquium

Time and Location:

Link:

Boolean circuits are one of the simplest and most natural models of computation. Despite their simplicity, many of the deepest open problems in complexity theory are basic questions about circuits. For example, the famous P ≠ NP conjecture asks whether the following circuit analysis problem is tractable: determine whether a given circuit ever outputs 1 (i.e., the Circuit-SAT problem).

In this talk, I will discuss my work answering multiple longstanding questions about the nature of circuits, including:

• Are there inherently sequential tasks that are far more costly to compute with highly parallel circuits? Our result gives exponentially stronger lower bounds than prior work and is the first progress in more than 30 years.
• How algorithmically difficult is it to find the smallest circuit computing a given function? This question dates back to Levin’s work on NP-completeness in 1973. 
• Is *every* circuit analysis problem (Circuit-SAT is just one example) intractable? We refute this 25-year-old conjecture.
• Can you prove that a circuit is satisfiable without revealing a satisfying input to the circuit? We show how to achieve this, and more, with an ordinary (non-interactive) proof, a dream result since “zero-knowledge proofs” were defined in 1985.

My work on these questions won five best student paper awards (ITCS '20, CCC '20, FOCS '20, FOCS '23, FOCS '25).