Iddo Tzameret

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

Collaborative distances:

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

2025

First-order reasoning and efficient semi-algebraic proofs.

Fedor Part, Neil Thapen, Iddo Tzameret

Ann. Pure Appl. Log., 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

Electron. Colloquium Comput. Complex., 2024

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

Albert Atserias, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2024

2023

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness.

Iddo Tzameret, Luming Zhang

Electron. Colloquium Comput. Complex., 2023

2022

Simple Hard Instances for Low-Depth Algebraic Proofs.

Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2022

2021

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

Rahul Santhanam, Iddo Tzameret

Electron. Colloquium Comput. Complex., 2021

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

Fedor Part, Iddo Tzameret

Comput. Complex., 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

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

Electron. Colloquium Comput. Complex., 2016

2015

Short Proofs for the Determinant Identities.

Pavel Hrubes, Iddo Tzameret

SIAM J. Comput., 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

Short propositional refutations for dense random 3CNF formulas.

Sebastian Müller, Iddo Tzameret

Ann. Pure Appl. Log., 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

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

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

Chic. J. Theor. Comput. Sci., 2013

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

Complexity of propositional proofs under a promise.

Nachum Dershowitz, Iddo Tzameret

ACM Trans. Comput. Log., 2010

Algebraic Proofs over Noncommutative Formulas.

Iddo Tzameret

Electron. Colloquium Comput. Complex., 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

2003

Gap Embedding for Well-Quasi-Orderings.

Nachum Dershowitz, Iddo Tzameret

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