1 citations · 1 across the 4 of their papers we have counts for
8 papers
Simple Hard Instances for Low-Depth Algebraic Proofs
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret
We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically,…
First-Order Reasoning and Efficient Semi-Algebraic Proofs
Fedor Part, Neil Thapen, Iddo Tzameret
Semi-algebraic proof systems such as sum-of-squares (SoS) have attracted a lot of attention recently due to their relation to approximation algorithms: constant degree semi-algebra…
Semi-Algebraic Proofs, IPS Lower Bounds and the -Conjecture: Can a Natural Number be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch +1
We introduce the binary value principle which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems…
Uniform, Integral and Feasible Proofs for the Determinant Identities
Iddo Tzameret, Stephen A. Cook
Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for…
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
Fedor Part, Iddo Tzameret
Resolution over linear equations is a natural extension of the popular resolution refutation system, augmented with the ability to carry out basic counting. Denoted Res(lin_R), thi…
Algebraic Proof Complexity: Progress, Frontiers and Challenges
Tonnian Pitassi, Iddo Tzameret
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…