Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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


TR24-079 | 20th April 2024
Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for
deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ... more >>>


TR25-134 | 19th September 2025
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret

AC$^0$[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard

We study whether lower bounds against constant-depth algebraic circuits computing the Permanent over finite fields (Limaye–Srinivasan–Tavenas [J. ACM, 2025] and Forbes [CCC’24]) are hard to prove in certain proof systems. We focus on a DNF formula that expresses that such lower bounds are hard for constant-depth algebraic proofs. Using an ... more >>>




ISSN 1433-8092 | Imprint