Iddo Tzameret:   Papers




        Under Submission/Review

Fedor Part and Iddo Tzameret Resolution with Counting: Lower Bounds over Different Moduli 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) 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

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

Iddo Tzameret Complexity, Proofs and Algebra Note. 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