Algebraic Proof Complexity: Progress, Frontiers and Challenges. / Pitassi, Tonnian; Tzameret, Iddo.

Electronic Colloquium on Computation Complexity . 2017.

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

Published

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
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 29034485