Iddo Tzameret Publications

        Under Submission

Iddo Tzameret and Lu-Ming Zhang Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness PDF | ECCC

        Published

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 To appear 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