Iddo Tzameret:   Papers




        Under Submission/Review

Fedor Part and Iddo Tzameret Resolution with Counting: Different Moduli and Tree-Like Lower Bounds Manuscript, 2018 [PDF]

Iddo Tzameret Sparser Random 3SAT Refutation Algorithms and the Interpolation Problem Electronic Colloquium on Computational Complexity TR13-070, 22 pages. Full version to be submitted to a journal publication, 2014. [PDF]


        Surveys & Book Chapters

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]


        Conference Publications

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]

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]

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]

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 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]

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 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]


        Journal Publications

Fu Li, Iddo Tzameret and Zhengyu Wang Characterizing Propositional Proofs as Non-commutative Formulas SIAM Journal on Computing (SICOMP) To appear, 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]

Michael Forbes, Amir Shpilka, Iddo Tzameret and Avi Wigderson Proof Complexity Lower Bounds from Algebraic Circuit Complexity Expected to appear in Theory of Computation (ToC) (Invited; special journal issue on CCC'16; DOI:10.4086/toc.2017. v013a001.) [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]

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]

Iddo Tzameret Algebraic Proofs over Noncommutative Formulas Information and Computation (I&C) 209 (10):1269-1292, 2011. [PDF]

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]

Nachum Dershowitz and Iddo Tzameret Complexity of Propositional Proofs under a Promise ACM Transactions on Computational Logic (ToCL) 11(3):1-29, 2010. [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 Gap Embedding for Well-Quasi-Orderings Electronic Notes in Theoretical Computer Science, Vol. 84. [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]


        Dissertations

Studies in Algebraic and Propositional Proof Complexity PhD thesis, Tel Aviv University, 2008. [PDF]

Kruskal-Friedman Gap Embedding Theorems Over Well-Quasi-Orderings M.Sc. thesis, School of Computer Science, Tel Aviv university. [PDF]