Iddo Tzameret

According to our database, Iddo Tzameret authored at least 36 papers between 2003 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

AC⁰[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard.

Jiaqi Lu, Rahul Santhanam, Iddo Tzameret

CoRR, September, 2025

Lower Bounds against the Ideal Proof System in Finite Fields.

Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2025

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets.

Albert Atserias, Iddo Tzameret

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

SIAM J. Comput., 2024

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

Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness.

Iddo Tzameret, Luming Zhang

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2022

Simple Hard Instances for Low-Depth Algebraic Proofs.

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Iterated lower bound formulas: a diagonalization-based approach to proof complexity.

Rahul Santhanam, Iddo Tzameret

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

First-Order Reasoning and Efficient Semi-Algebraic Proofs.

Fedor Part, Neil Thapen, Iddo Tzameret

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Resolution with Counting: Dag-Like Lower Bounds and Different Moduli.

Fedor Part, Iddo Tzameret

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

From Classical Proof Theory to P versus NP: a Guide to Bounded Theories (Invited Talk).

Iddo Tzameret

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

2019

Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2019

2018

Characterizing Propositional Proofs as Noncommutative Formulas.

Fu Li, Iddo Tzameret, Zhengyu Wang

SIAM J. Comput., 2018

Witnessing matrix identities and proof complexity.

Fu Li, Iddo Tzameret

Int. J. Algebra Comput., 2018

Uniform, Integral and Feasible Proofs for the Determinant Identities.

Iddo Tzameret, Stephen A. Cook

Electron. Colloquium Comput. Complex., 2018

Resolution with Counting: Lower Bounds over Different Moduli.

Fedor Part, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2018

2017

Uniform, integral and efficient proofs for the determinant identities.

Iddo Tzameret, Stephen A. Cook

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

2016

Algebraic Proof Complexity: Progress, Frontiers and Challenges.

Toniann Pitassi, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Characterizing Propositional Proofs as Non-Commutative Formulas.

Fu Li, Iddo Tzameret, Zhengyu Wang

Electron. Colloquium Comput. Complex., 2015

Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs.

Fu Li, Iddo Tzameret, Zhengyu Wang

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem - (Extended Abstract).

Iddo Tzameret

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation.

Iddo Tzameret

Electron. Colloquium Comput. Complex., 2013

Generating Matrix Identities and Proof Complexity Lower Bounds.

Fu Li, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2013

2012

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic.

Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2012

Short proofs for the determinant identities.

Pavel Hrubes, Iddo Tzameret

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Short Propositional Refutations for Dense Random 3CNF Formulas.

Sebastian Müller, Iddo Tzameret

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

2011

Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas.

Sebastian Müller, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2011

2010

Algebraic Proofs over Noncommutative Formulas.

Iddo Tzameret

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

2009

The Proof Complexity of Polynomial Identities.

Pavel Hrubes, Iddo Tzameret

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Studies in algebraic and propositional proof complexity

Iddo Tzameret

PhD thesis, 2008

The Strength of Multilinear Proofs.

Ran Raz, Iddo Tzameret

Comput. Complex., 2008

2007

Resolution over Linear Equations and Multilinear Proofs.

Ran Raz, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2007

Complexity of Propositional Proofs Under a Promise.

Nachum Dershowitz, Iddo Tzameret

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2003

Gap Embedding for Well-Quasi-Orderings.

Nachum Dershowitz, Iddo Tzameret

Proceedings of the 10th Workshop on Logic, Language, Information and Computation, 2003