Professor Iddo Tzameret

  1. 2020
  2. 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

  3. 2019
  4. Published

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

    Yaroslav, A., Grigoriev, D., Hirsch, E. & Tzameret, I., 10 Sep 2019, 56 p.

    Research output: Other contribution

  5. 2018
  6. 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

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

  8. 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

  9. Unpublished

    Complexity, Proofs and Algebra

    Tzameret, I., 2018, (Unpublished)

    Research output: Other contribution

  10. 2017
  11. 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

  12. 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

  13. 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

  14. 2016
  15. 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

  16. 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

  17. 2015
  18. Published
  19. 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

  20. 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

  21. 2014
  22. 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

  23. 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

  24. Published

    Generating Matrix Identities and Proof Complexity

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

    Research output: Contribution to conferencePaper

  25. 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

  26. 2013
  27. Published

    Refuting Random 3CNF Formulas in Propositional Logic

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

    Research output: Contribution to conferencePaper

  28. 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

  29. 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

  30. 2012
  31. 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

  32. 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

  33. 2011
  34. 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

  35. 2010
  36. 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

  37. 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

  38. 2009
  39. 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

  40. 2008
  41. 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

  42. Published

    Studies in Algebraic and Propositional Proof Complexity

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

    Research output: ThesisDoctoral Thesis

  43. Published

    The Strength of Multilinear Proofs

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

    Research output: Contribution to journalArticle

  44. 2007
  45. Published

    Complexity of Propositional Proofs under a Promise

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

    Research output: Contribution to conferencePaper