Algebraic proof complexity

Toniann Pitassi, Iddo Tzameret

ACM SIGLOG News · 2016 · 13 citations · 35 references

DOIFull text

Open access

Concepts

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.

References

35