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

Standard

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

Harvard

APA

Vancouver

Pitassi T, Tzameret I. Algebraic Proof Complexity: Progress, Frontiers and Challenges. In Electronic Colloquium on Computation Complexity . 2017

Author

Pitassi, Tonnian ; Tzameret, Iddo. / Algebraic Proof Complexity: Progress, Frontiers and Challenges. Electronic Colloquium on Computation Complexity . 2017.

BibTeX

@inproceedings{bb53502cbb3e483d96d19cde3f154e9a,
title = "Algebraic Proof Complexity: Progress, Frontiers and Challenges",
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.",
author = "Tonnian Pitassi and Iddo Tzameret",
year = "2017",
language = "English",
booktitle = "Electronic Colloquium on Computation Complexity",

}

RIS

TY - GEN

T1 - Algebraic Proof Complexity: Progress, Frontiers and Challenges

AU - Pitassi, Tonnian

AU - Tzameret, Iddo

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

M3 - Conference contribution

BT - Electronic Colloquium on Computation Complexity

ER -