Algorithmic Proofs of Algorithmic Impossibility

The project will exploit and strengthen synergies between algorithms and lower bounds in order to make progress in major questions in circuit complexity and the theories of cryptography and learning. The main objectives are the following:

I. Frontier circuit lower bounds: To develop methods based on combinatorics and discrete analysis to solve longstanding open questions in circuit complexity, making progress towards showing that P is not equal to NP.

II. Lower bounds for algorithms: To strengthen the algorithmic consequences of proofs of lower bounds, applying modern combinatorial constructions. Besides new learning algorithms, this direction can refute heuristic cryptographic constructions which were recently proposed.

III. A theory of quantum meta-complexity: To develop the above synergies in the context of quantum computing, a very timely investigation in view of the rise of quantum cryptography. This includes circuit lower bounds from quantum algorithms, and connections between quantum learning and quantum cryptography.