Iddo Tzameret

Publication Activity (10 Years)

Years Active: 2003-2025
Publications (10 Years): 35

Top Topics

Extended Abstract

Top Venues

Electron. Colloquium Comput. Complex.

SIAM J. Comput.

Publications

Fedor Part, Neil Thapen, Iddo Tzameret
First-order reasoning and efficient semi-algebraic proofs. Ann. Pure Appl. Log. 176 (1) (2025)
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. STOC (2024)
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. Electron. Colloquium Comput. Complex. (2024)
Iddo Tzameret, Luming Zhang
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. ITCS (2024)
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative? SIAM J. Comput. 53 (3) (2024)
Iddo Tzameret, Lu-Ming Zhang
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. CoRR (2023)
Iddo Tzameret, Luming Zhang
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. Electron. Colloquium Comput. Complex. (2023)
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret
Simple Hard Instances for Low-Depth Algebraic Proofs. FOCS (2022)
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret
Simple Hard Instances for Low-Depth Algebraic Proofs. CoRR (2022)
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret
Simple Hard Instances for Low-Depth Algebraic Proofs. Electron. Colloquium Comput. Complex. (2022)
Fedor Part, Iddo Tzameret
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. Comput. Complex. 30 (1) (2021)
Iddo Tzameret, Stephen A. Cook
Uniform, Integral, and Feasible Proofs for the Determinant Identities. J. ACM 68 (2) (2021)
Fedor Part, Neil Thapen, Iddo Tzameret
First-Order Reasoning and Efficient Semi-Algebraic Proofs. LICS (2021)
Rahul Santhanam, Iddo Tzameret
Iterated lower bound formulas: a diagonalization-based approach to proof complexity. STOC (2021)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Theory Comput. 17 (2021)
Rahul Santhanam, Iddo Tzameret
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Fedor Part, Neil Thapen, Iddo Tzameret
First-Order Reasoning and Efficient Semi-Algebraic Proofs. CoRR (2021)
Iddo Tzameret
From Classical Proof Theory to P versus NP: a Guide to Bounded Theories (Invited Talk). CSL (2020)
Fedor Part, Iddo Tzameret
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. ITCS (2020)
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? STOC (2020)
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture: Can a Natural Number be Negative? CoRR (2019)
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret
Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative? Electron. Colloquium Comput. Complex. 26 (2019)
Fu Li, Iddo Tzameret
Witnessing matrix identities and proof complexity. Int. J. Algebra Comput. 28 (2) (2018)
Iddo Tzameret, Stephen A. Cook
Uniform, Integral and Feasible Proofs for the Determinant Identities. Electron. Colloquium Comput. Complex. 25 (2018)
Iddo Tzameret, Stephen A. Cook
Uniform, Integral and Feasible Proofs for the Determinant Identities. CoRR (2018)
Fu Li, Iddo Tzameret, Zhengyu Wang
Characterizing Propositional Proofs as Noncommutative Formulas. SIAM J. Comput. 47 (4) (2018)
Fedor Part, Iddo Tzameret
Resolution with Counting: Lower Bounds over Different Moduli. Electron. Colloquium Comput. Complex. 25 (2018)
Fedor Part, Iddo Tzameret
Resolution with Counting: Lower Bounds over Different Moduli. CoRR (2018)
Iddo Tzameret, Stephen A. Cook
Uniform, integral and efficient proofs for the determinant identities. LICS (2017)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Computational Complexity Conference (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CoRR (2016)
Toniann Pitassi, Iddo Tzameret
Algebraic Proof Complexity: Progress, Frontiers and Challenges. CoRR (2016)
Toniann Pitassi, Iddo Tzameret
Algebraic proof complexity: progress, frontiers and challenges. ACM SIGLOG News 3 (3) (2016)
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Toniann Pitassi, Iddo Tzameret
Algebraic Proof Complexity: Progress, Frontiers and Challenges. Electron. Colloquium Comput. Complex. 23 (2016)
Fu Li, Iddo Tzameret, Zhengyu Wang
Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs. Computational Complexity Conference (2015)
Pavel Hrubes, Iddo Tzameret
Short Proofs for the Determinant Identities. SIAM J. Comput. 44 (2) (2015)
Fu Li, Iddo Tzameret, Zhengyu Wang
Characterizing Propositional Proofs as Non-Commutative Formulas. Electron. Colloquium Comput. Complex. 22 (2015)
Sebastian Müller, Iddo Tzameret
Short propositional refutations for dense random 3CNF formulas. Ann. Pure Appl. Log. 165 (12) (2014)
Iddo Tzameret
Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem - (Extended Abstract). ICALP (1) (2014)
Fu Li, Iddo Tzameret, Zhengyu Wang
Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs. CoRR (2014)
Iddo Tzameret
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation. Electron. Colloquium Comput. Complex. 20 (2013)
Iddo Tzameret
On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation CoRR (2013)
Fu Li, Iddo Tzameret
Generating Matrix Identities and Proof Complexity Lower Bounds. Electron. Colloquium Comput. Complex. 20 (2013)
Fu Li, Iddo Tzameret
Generating Matrix Identities and Proof Complexity Lower Bounds. CoRR (2013)
Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. Chic. J. Theor. Comput. Sci. 2013 (2013)
Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. Electron. Colloquium Comput. Complex. 19 (2012)
Pavel Hrubes, Iddo Tzameret
Short proofs for the determinant identities. STOC (2012)
Sebastian Müller, Iddo Tzameret
Short Propositional Refutations for Dense Random 3CNF Formulas. LICS (2012)
Iddo Tzameret
Algebraic proofs over noncommutative formulas. Inf. Comput. 209 (10) (2011)
Pavel Hrubes, Iddo Tzameret
Short Proofs for the Determinant Identities. Electron. Colloquium Comput. Complex. 18 (2011)
Sebastian Müller, Iddo Tzameret
Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas CoRR (2011)
Pavel Hrubes, Iddo Tzameret
Short Proofs for the Determinant Identities CoRR (2011)
Sebastian Müller, Iddo Tzameret
Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas. Electron. Colloquium Comput. Complex. 18 (2011)
Nachum Dershowitz, Iddo Tzameret
Complexity of propositional proofs under a promise. ACM Trans. Comput. Log. 11 (3) (2010)
Iddo Tzameret
Algebraic Proofs over Noncommutative Formulas. TAMC (2010)
Iddo Tzameret
Algebraic Proofs over Noncommutative Formulas. Electron. Colloquium Comput. Complex. 17 (2010)
Iddo Tzameret
Algebraic Proofs over Noncommutative Formulas CoRR (2010)
Pavel Hrubes, Iddo Tzameret
The Proof Complexity of Polynomial Identities. Computational Complexity Conference (2009)
Ran Raz, Iddo Tzameret
The Strength of Multilinear Proofs. Comput. Complex. 17 (3) (2008)
Ran Raz, Iddo Tzameret
Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Log. 155 (3) (2008)
Ran Raz, Iddo Tzameret
Resolution over Linear Equations and Multilinear Proofs. Electron. Colloquium Comput. Complex. 14 (078) (2007)
Nachum Dershowitz, Iddo Tzameret
Complexity of Propositional Proofs Under a Promise. ICALP (2007)
Nachum Dershowitz, Iddo Tzameret
Complexity of Propositional Proofs under a Promise CoRR (2007)
Ran Raz, Iddo Tzameret
Resolution over Linear Equations and Multilinear Proofs CoRR (2007)
Ran Raz, Iddo Tzameret
The Strength of Multilinear Proofs Electron. Colloquium Comput. Complex. (001) (2006)
Nachum Dershowitz, Iddo Tzameret
Gap Embedding for Well-Quasi-Orderings. Electron. Notes Theor. Comput. Sci. 84 (2003)