Colloquium Details
Computational Complexity and the Nature of Circuits
Speaker: Rahul Ilango, The Institute for Advanced Study
Location: 60 Fifth Avenue 150
Date: March 9, 2026, 2 p.m.
Host: Subhash Khot, Aaron Bernstein
Synopsis:
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).
Speaker Bio:
Rahul Ilango is a postdoc at the Institute for Advanced Study. He completed his PhD at MIT, advised by Ryan Williams and supported by an NSF Graduate Research Fellowship. His research focuses on questions in computational complexity theory and proof complexity. His work has won five best student paper awards and has been featured in both Quanta Magazine and Scientific American.
Notes:
In-person attendance only available to those with active NYU ID cards.