The
P = NP
problem asks whether every computational problem for which a solution can
be efficiently verified can also be efficiently solved.
Counted among the 7 Clay Millennium Prize Problems,
it is one of the most influential unsolved problems of mathematics,
with implications for biology, cryptography, and many other fields.
(Read more about the P vs. NP problem
here.)
Boolean circuit computing the Boolean function
f : {0,1}3 → {0,1}
such that
f(x1,x2,x3)
=
¬x1 ∧ (x2 ∨ x3).
Boolean circuits model computation as a sequence of simple, local steps,
called gates,
and the efficiency of the circuit is measured by its
size (number of gates).
One of the most promising approaches to solve the P vs NP problem is via
circuit lower bounds,
a proof of impossibility which shows that
no circuit of small size can solve a concrete problem of interest.
A sufficiently strong circuit lower bound is enough to conclude that
P ≠ NP, thus solving the question.
Most of the success in the investigation of circuits has been on
restricted
types of circuits.
Investigating such models allows us to understand the power
and limitations of particular families of algorithms,
en route to understanding computation at large.
Over the years, this study has unveiled a beautiful synergy between
circuit lower bounds, combinatorics, and algorithms.
For instance,
algorithms can imply lower bounds
[i
Ryan Williams.
Nonuniform ACC circuit lower bounds.
Journal of the ACM, 2014.
],
and proofs of lower bounds can contain algorithms
[ii
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.
Learning algorithms from natural proofs.
CCC, 2016.
].
The project will exploit and strengthen those connections
to obtain new circuit lower bounds,
and find new ways to extract algorithms from lower bounds.
It will also develop those ideas in the context of
quantum computing,
where they are less understood.
We construct polynomials that can be computed efficiently
using additions, subtractions and multiplications, but such that
computing any of their powers without subtractions requires an
exponential number of gates.
We show that there are certain tasks that no computer can “learn” efficiently,
assuming well-established complexity-theoretic hypotheses.
Our proof brings a novel connection between the hardness of
learning, communicating, and automatically finding mathematical proofs.
Bruno P. Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov.
Monotone circuit complexity of matching.
STOC, 2026.
Simple explanation
We show that Boolean circuits without negations (monotone circuits)
deciding if a graph has a “perfect matching”
must have exponential size, settling a 40-year-old question.
Our work also
separates constant-depth and monotone circuits, solving an open question from the
90s.
We study what cryptographic conditions make
“distribution verification” (i.e., checking if an unknown distribution is close to a known one) possible.
As an application of our techniques,
we give a procedure for classical
computers to verify,
with only a polynomial number of samples, whether a quantum computer is
sampling from a distribution that classical computers cannot.