Algebraic Proof Complexity: Progress, Frontiers and Challenges

Tonnian Pitassi, Iddo Tzameret

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight connections between proof complexity lower bounds (namely, lower bounds on the size of proofs of certain tautologies), algebraic circuit lower bounds, and the Polynomial Identity Testing problem from derandomization theory.
Original languageEnglish
Title of host publicationElectronic Colloquium on Computation Complexity
Publication statusPublished - 2017

Cite this