Algorithmic Proofs of Algorithmic Impossibility

Counted among the 7 Clay Millenium Prize problems, the P vs. NP problem is one of the most influential unsolved problems of mathematics, with far-reaching implications for biology, cryptography, operations research, and many other fields. At heart, this question is concerned with the inherent mathematical limits of computational devices. If P = NP, then incredible algorithms are possible, though this also means that several real-world cryptographic systems are insecure. It is however widely believed that P is not equal to NP, and proving this conjecture amounts to a proof that it is impossible to design efficient algorithms for certain problems. The main purpose of the project is to make progress into such "proofs of algorithmic impossibility", while leveraging and further developing the apparently paradoxical phenomenon that such proofs often embed algorithms into themselves.
One of the most promising approaches to solve the P vs NP problem is via Boolean circuits, a mathematical abstraction that captures the essential computational capabilities of everyday digital circuits. 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). Circuit lower bounds are an impossibility result 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 is not equal to NP, solving the question.
Most of the success in the investigation of circuits has been on restricted circuit models. Such models provide a precise mathematical formalism of specific types of algorithms, allowing us to investigate their power and limitations en-route to understanding computation at large. Along the years, this study has unveiled a beautiful synergy between circuits, mathematics, and algorithms. First, many proofs of circuit lower bounds have both drawn from and contributed to extremal and probabilistic...