Professor Iddo Tzameret

  1. 2020
  2. Published

    Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture: Can a Natural Number be Negative?

    Yaroslav, A., Grigoriev, D., Hirsch, E. & Tzameret, I., Jun 2020, Proceedings of the 52th Annual ACM Symposium on the Theory of Computing (STOC), 2020. Association for Computing Machinery (ACM), Vol. 52. p. 54-67 14 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Published

    From classical proof theory to P vs. NP: a guide to bounded theories

    Tzameret, I., 14 Jan 2020, 28th EACSL Annual Conference on Computer Science Logic (CSL) 2020, January 13-16, 2020, Barcelona, Spain. : LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2020. .

    Research output: Chapter in Book/Report/Conference proceedingOther contribution

  4. 2018
  5. Forthcoming

    Resolution with Counting: Dag and Tree-like Lower Bounds over Different Moduli

    Part, F. & Tzameret, I., 18 May 2018, (Accepted/In press).

    Research output: Contribution to conferenceAbstract

  6. Published

    Witnessing matrix identities and proof complexity

    Li, F. & Tzameret, I., 26 Feb 2018, In : International Journal of Algebra and Computation. 28, 2, p. 217–256 40 p.

    Research output: Contribution to journalArticle

  7. Published

    Characterizing Propositional Proofs as Non-commutative Formulas

    Li, F., Tzameret, I. & Wang, Z., 2018, In : SIAM Journal on Computing. 47, 4, p. 1424-1462 39 p.

    Research output: Contribution to journalArticle

  8. Unpublished

    Complexity, Proofs and Algebra

    Tzameret, I., 2018, (Unpublished)

    Research output: Other contribution

  9. 2017
  10. Published

    Proof Complexity Lower Bounds from Algebraic Circuit Complexity

    Forbes, M., Shpilka, A., Tzameret, I. & Wigderson, A., 1 Oct 2017, Theory of Computation (ToC) . p. 1 78 p.

    Research output: Chapter in Book/Report/Conference proceedingOther contribution

  11. Published

    Uniform, integral and efficient proofs for the determinant identities

    Tzameret, I. & Cook, S., 18 Aug 2017, Logic in Computer Science (LICS), 2017 32nd Annual ACM/IEEE Symposium on. IEEE, Vol. 32. p. 1-12 12 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  12. Published

    Algebraic Proof Complexity: Progress, Frontiers and Challenges

    Pitassi, T. & Tzameret, I., 2017, Electronic Colloquium on Computation Complexity .

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  13. 2016
  14. Published

    Algebraic Proof Complexity: Progress, Frontiers and Challenges

    Pitassi, T. & Tzameret, I., 8 Jul 2016, ACM SIGLOG News. Immerman, N. (ed.). New York: ACM, Vol. 3. p. 21-43 23 p.

    Research output: Chapter in Book/Report/Conference proceedingOther contribution

  15. Published

    Proof complexity lower bounds from algebraic circuit complexity

    Forbes, M., Shpilka, A., Tzameret, I. & Wigderson, A., 2016, 31st Conference on Computational Complexity (CCC 2016). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Vol. 50. p. 32:1-32:17 17 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 50).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  16. 2015
  17. Published
  18. E-pub ahead of print

    Short Proofs for the Determinant Identities

    Hrubes, P. & Tzameret, I., 7 Apr 2015, In : SIAM Journal on Computing. 44, 2, p. 340–383 44 p.

    Research output: Contribution to journalArticle

  19. Unpublished

    Håstad‘s Separation of Constant-Depth Circuits Using Sipser Functions

    Tzameret, I., 2015, (Unpublished) Expository Note. 15 p.

    Research output: Book/ReportOther report

  20. 2014
  21. Published

    Non-commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs

    Li, F., Tzameret, I. & Wang, Z., 30 Dec 2014, ArXiV. p. 1 32 p.

    Research output: Chapter in Book/Report/Conference proceedingOther contribution

  22. Published

    Sparser Random 3SAT Refutation Algorithms and the Interpolation Problem: Extended Abstract

    Tzameret, I., 8 Jul 2014, Automata, Languages, and Programming - 41st International Colloquium, (ICALP) 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part {I}: --. p. 1015-1026 12 p. (LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  23. Published

    Generating Matrix Identities and Proof Complexity

    Li, F. & Tzameret, I., 2014, p. 1-46. 46 p.

    Research output: Contribution to conferencePaper

  24. Published

    Short Propositional Refutations for Dense Random 3CNF Formulas

    Muller, S. & Tzameret, I., 2014, In : Annals of Pure and Applied Logic. 165, p. 1864-1918 55 p.

    Research output: Contribution to journalArticle

  25. 2013
  26. Published

    Refuting Random 3CNF Formulas in Propositional Logic

    Muller, S. & Tzameret, I., Oct 2013, p. 201. 208 p.

    Research output: Contribution to conferencePaper

  27. Published

    Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

    Allender, E., Davie, G., Friedman, L., Hopkins, S. & Tzameret, I., 2013, In : Chicago Journal of Theoretical Computer Science. 5, p. 1-15 15 p.

    Research output: Contribution to journalArticle

  28. Published

    Proving Random Formulas in Propositional Logic

    Tzameret, I. & Muller, S., 2013, Logic Across the University: Foundations and Application: Proceedings of the Tsinghua Logic Conference. van Benthem, J. & Liu, F. (eds.). London: College Publications London, Vol. 47. p. 201-208 8 p. (Studies in Logic).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  29. 2012
  30. Published

    Short Propositional Refutations for Dense Random 3CNF Formulas

    Muller, S. & Tzameret, I., Jun 2012, Proceedings of the 27th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS): 25-28 June 2012. p. 501-510 10 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  31. Published

    Short Proofs for the Determinant Identities

    Hrubes, P. & Tzameret, I., 19 May 2012, Proceedings of the 44th Annual ACM Symposium on the Theory of Computing (STOC). p. 193-212

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  32. 2011
  33. Published

    Algebraic Proofs over Noncommutative Formulas

    Tzameret, I., 2011, In : Information and Computation. 209, 10, p. 1269-1292 24 p.

    Research output: Contribution to journalArticle

  34. 2010
  35. Published

    Algebraic Proofs over Noncommutative Formulas

    Tzameret, I., 2010, 7th Annual Conference on Theory and Applications of Models of Computation. Berlin, Vol. 6108. p. 60 71 p. (Lecture Notes in Computer Science (LNCS)).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  36. Published

    Complexity of Propositional Proofs Under a Promise

    Dershowitz, N. & Tzameret, I., 2010, In : ACM Transactions on Computational Logic. 11, 3, p. 1-30 30 p.

    Research output: Contribution to journalArticle

  37. 2009
  38. Published

    The Proof Complexity of Polynomial Identities

    Hrubes, P. & Tzameret, I., 2009, Proceedings of the 24th IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press, p. 41-51 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  39. 2008
  40. Published

    Resolution over Linear Equations and Multilinear Proofs

    Raz, R. & Tzameret, I., 2008, In : Annals of Pure and Applied Logic. 155, 3, p. 194-224 31 p.

    Research output: Contribution to journalArticle

  41. Published

    Studies in Algebraic and Propositional Proof Complexity

    Tzameret, I., 2008, Tel Aviv. 214 p.

    Research output: ThesisDoctoral Thesis

  42. Published

    The Strength of Multilinear Proofs

    Raz, R. & Tzameret, I., 2008, In : Computational Complexity. 17, 3, 51 p.

    Research output: Contribution to journalArticle

  43. 2007
  44. Published

    Complexity of Propositional Proofs under a Promise

    Dershowitz, N. & Tzameret, I., 2007. 30 p.

    Research output: Contribution to conferencePaper