Published
Tuomas Hakoniemi, Nutan Limaye and Iddo Tzameret
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
To appear in
56th Annual ACM Symposium on Theory of Computing
(STOC), Vancouver, June 2024.
Manuscript, 2023.
PDF (NEW)
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch and Iddo Tzameret
Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture:
Can a Natural Number be Negative?
To appear in SIAM Journal on Computing (SICOMP), 2024.
PDF
| DOI
Iddo Tzameret and Lu-Ming Zhang
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
In proceedings of 15th Innovations in Theoretical Computer Science Conference (ITCS) 2024, January, 2024, Berkeley, CA, USA.
Electronic Colloquium on Computational Complexity TR23-057, 2023.
PDF
| ECCC
Nashlen Govindasamy, Tuomas Hakoniemi and Iddo Tzameret
Simple Hard Instances for Low-Depth Algebraic Proofs
In Symp. on Found. Computer Science (FOCS), 2022.
PDF
|
DOI
Rahul Santhanam and Iddo Tzameret
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
In 53rd Annual ACM Symposium on Theory of Computing
(STOC), Rome, June 2021.
Invited to SIAM J. Comput. special issue.
PDF |
STOC Video
Fedor Part, Neil Thapen and Iddo Tzameret
First-Order Reasoning and Efficient Semi-Algebraic Proofs
In
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic In Computer
Science
(LICS), June 2021.
PDF |
Fedor's Video
Michael Forbes, Amir Shpilka, Iddo Tzameret and Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Theory of Computing (ToC), Vol. 17, no.10, 1-88, 2021.
(Invited; special journal issue on CCC'16; DOI:10.4086/toc.2021.v017a010)
PDF
| DOI
Fedor Part and Iddo Tzameret
Resolution with Counting: Different Moduli and Dag-Like Lower Bounds
Comput. Complex. (CC), Springer Birkhäuser, (2021) 30:2.
PDF
| DOI
Iddo Tzameret and Stephen A. Cook
Uniform, Integral and Feasible Proofs for the Determinant Identities
Journal of the ACM (JACM), Vol. 68, No. 2 (2021).
PDF
| DOI
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch and Iddo Tzameret
Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture:
Can a Natural Number be Negative?
In proceedings of
52nd Annual ACM Symposium on Theory of Computing
(STOC), Chicago, IL, June 22-26, 2020.
PDF
| DOI
Fedor Part and Iddo Tzameret
Resolution with Counting: Different Moduli and Dag-Like Lower Bounds
In proceedings of 11th Innovations in Theoretical Computer Science Conference (ITCS) 2020, January, 2020, Seattle, WA, USA.
Electronic Colloquium on Computational Complexity TR18-117, 2018.
PDF
|
DOI
Iddo Tzameret
From classical proof theory to P vs. NP: A Guide to Bounded Theories.
28th EACSL Annual Conference on Computer Science Logic (CSL) 2020, January 13-16, 2020, Barcelona, Spain. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2020.
Fu Li, Iddo Tzameret and Zhengyu Wang
Characterizing Propositional Proofs as Non-commutative Formulas
SIAM Journal on Computing (SICOMP) 47(4), pp. 1424-1462, 2018.
PDF
Fu Li and Iddo Tzameret
Witnessing Matrix Identities and Proof Complexity
Int. J. Algebra Comput. (IJAC) 28 (2), pp. 217-256. World Scientific, 2018.
PDF
Iddo Tzameret and Stephen A. Cook
Uniform, Integral and Efficient Proofs for the Determinant Identities
In
Proceedings of the 32th Annual ACM/IEEE Symposium on Logic In Computer
Science
(LICS), 20-23 June 2017.
Invited to the Journal of the ACM (JACM)
PDF
Tonnian Pitassi and Iddo Tzameret
Algebraic Proof Complexity: Progress, Frontiers and Challenges
ACM SIGLOG News (SIGLOG), 3 (3), pp. 21-43, ACM New York, July
2016.
PDF
Michael Forbes, Amir Shpilka, Iddo Tzameret and Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
In Proceedings of the 31th Annual Computational Complexity Conference (CCC):
June 16-18, 2016.
Invited to the special journal issue on CCC'16 (Theory Comput. ToC)
PDF
Fu Li, Iddo Tzameret and Zhengyu Wang
Non-commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs
In Proceedings of the 30th Annual Computational Complexity Conference (CCC):
June 17-19, 2015.
Invited to the special journal issue on CCC'15 (Comput. Complexity CC).
PDF
Pavel Hrubeš and Iddo Tzameret
Short Proofs for the Determinant Identities
SIAM Journal on Computing (SICOMP) 44 (2015), No. 2, pp. 340-383.
PDF
Sebastian Müller and Iddo Tzameret
Short Propositional Refutations for Dense Random 3CNF Formulas
Annals of Pure and Applied Logic (APAL) 165(12):1864-1918 (2014).
PDF
Iddo Tzameret
Sparser Random 3SAT Refutation Algorithms and the Interpolation Problem
Preliminary version in Proceedings of the 41st International Colloquium on Automata,
Languages and Programming (ICALP) track A, July 2014.
PDF
Eric Allender, George Davie, Luke Friedman, Sam Hopkins and Iddo Tzameret
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic
Chicago Journal of Theoretical Computer Science (CJTCS) (5): 1-15, 2013.
Preprint in ECCC 2012.
PDF
Sebastian Müller and Iddo Tzameret
Proving Random Formulas in Propositional Logic
In Johan van Benthem and Fenrong Liu, eds. Logic Across the University:
Foundations and Application, Proceedings of the Tsinghua Logic Conference, pp. 201-208.
Volume 47: Studies in Logic. College Publications London, 2013.
PDF
Pavel Hrubeš and Iddo Tzameret
Short Proofs for the Determinant Identities
In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing (STOC), pp.193-212. 19-22 May 2012.
PDF
Sebastian Müller and Iddo Tzameret
Short Propositional Refutations for Dense Random 3CNF Formulas
Proceedings of the 27th Annual ACM/IEEE Symposium on Logic In Computer
Science
(LICS), pp. 501-510. 25-28 June 2012.
Preprint in
ECCC.
PDF
Iddo Tzameret
Algebraic Proofs over Noncommutative Formulas
Information and Computation (I&C) 209 (10):1269-1292, 2011.
PDF
Nachum Dershowitz and Iddo Tzameret
Complexity of Propositional Proofs under a Promise
ACM Transactions on Computational Logic (ToCL) 11(3):1-29, 2010.
PDF
Iddo Tzameret
Algebraic Proofs over Noncommutative Formulas
invited to The 7th Annual Conference on
Theory and Applications of Models of Computation, June 7-11,
2010. Volume 6108 of Lecture Notes in Comput. Sci., pp. 60-71. Springer,
Berlin.
PDF
Pavel Hrubeš and Iddo Tzameret
The Proof Complexity of Polynomial Identities
Proceedings of the 24th IEEE Conference on Computational Complexity (CCC), pp. 41-51, 15-18 July 2009.
PDF
| Conference Version
Ran Raz and Iddo Tzameret
Resolution over Linear Equations and Multilinear Proofs
Annals of Pure and Applied Logic (APAL)
155(3):194-224, 2008.
Preliminary version in
ECCC 2007
and
[arXiv]
[doi:10.1016/j.apal.2008.04.001]
PDF
Ran Raz and Iddo Tzameret
The Strength of Multilinear Proofs
Computational Complexity (CC) 17(3) October, 2008.
Preliminary version in
ECCC 2006.
[doi:10.1007/s00037-008-0246-0]
PDF
Nachum Dershowitz and Iddo Tzameret
Complexity of Propositional Proofs under a Promise
Preliminary version in Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP) track A, pp. 9-13 July 2007.
PDF
Nachum Dershowitz and Iddo Tzameret
Gap Embedding for Well-Quasi-Orderings
Electronic Notes in Theoretical Computer Science, Vol. 84.
PDF
Nachum Dershowitz and Iddo Tzameret
Gap Embedding for Well-Quasi-Orderings
Proceedings of the 10th Workshop on Logic, Language, Information and Computation (WoLLIC '03).
PDF
Nachum Dershowitz and Iddo Tzameret
Quasi-Ordered Gap Embedding
Extended Abstracts of the International Workshop on Termination. (WST '03), Valencia, Spain.
PDF
Notes
Iddo Tzameret
Håstad‘s Separation of Constant-Depth Circuits Using Sipser Functions
Apr. 2009. (Updated Oct. 2012)
PDF
Iddo Tzameret
On the Structure and Complexity of Symbolic Proofs of Polynomial Identities
Manuscript, April 2008. Subsumed (and improved) in the above paper with P. Hrubeš.
PDF
Iddo Tzameret
A Concise Research Summary
Note, January 2017
PDF
Iddo Tzameret
Complexity, Proofs and Algebra
Note.
PDF
Dissertations
Studies in Algebraic and Propositional Proof Complexity
PhD thesis, Tel Aviv University, preliminary submission 2008 (diploma conferred 2010).
PDF
Kruskal-Friedman Gap Embedding Theorems
Over Well-Quasi-Orderings
M.Sc. thesis, School of Computer Science, Tel Aviv university.
PDF