Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > IPS:
Reports tagged with IPS:
TR16-101 | 1st July 2016
Toniann Pitassi, Iddo Tzameret

#### Algebraic Proof Complexity: Progress, Frontiers and Challenges

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

TR21-138 | 23rd September 2021
Rahul Santhanam, Iddo Tzameret

#### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>

ISSN 1433-8092 | Imprint