☰

Toni Pitassi - Publications

Affiliations: 
Computer Science University of Toronto, Toronto, ON, Canada 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

32 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2016 Pitassi T, Rossman B, Tan LY, Servedio RA. Poly-logarithmic Frege depth lower bounds via an expander switching lemma Proceedings of the Annual Acm Symposium On Theory of Computing. 19: 644-657. DOI: 10.1145/2897518.2897637  0.304
2016 Göös M, Pitassi T, Watson T. Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication Algorithmica. 1-36. DOI: 10.1007/S00453-015-0104-9  0.309
2015 Filmus Y, Pitassi T, Santhanam R. Exponential lower bounds for AC<sup>0</sup>-Frege imply superpolynomial Frege lower bounds Acm Transactions On Computation Theory. 7. DOI: 10.1145/2656209  0.569
2015 Wu Y, Austrin P, Pitassi T, Liu D. Inapproximability of treewidth and related problems Ijcai International Joint Conference On Artificial Intelligence. 2015: 4222-4228.  0.319
2014 Göös M, Pitassi T. Communication lower bounds via critical block sensitivity Proceedings of the Annual Acm Symposium On Theory of Computing. 847-856. DOI: 10.1145/2591796.2591838  0.404
2014 Ada A, Chattopadhyay A, Cook SA, Fontes L, Koucký M, Pitassi T. The hardness of being private Acm Transactions On Computation Theory. 6. DOI: 10.1145/2567671  0.313
2014 Grochow JA, Pitassi T. Circuit complexity, proof complexity, and polynomial identity testing Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 110-119. DOI: 10.1109/FOCS.2014.20  0.409
2013 Filmus Y, Pitassi T, Robere R, Cook SA. Average case lower bounds for monotone switching networks Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 598-607. DOI: 10.1109/FOCS.2013.70  0.479
2013 Maciel A, Nguyen P, Pitassi T. Lifting lower bounds for tree-like proofs Computational Complexity. 1-52. DOI: 10.1007/s00037-013-0064-x  0.378
2011 Filmus Y, Pitassi T, Santhanam R. Exponential lower bounds for AC0-frege imply superpolynomial frege lower bounds Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6755: 618-629. DOI: 10.1145/2656209  0.574
2011 Huang L, Pitassi T. Automatizability and simple stochastic games Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6755: 605-617. DOI: 10.1007/978-3-642-22006-7_51  0.308
2009 Pitassi T, Segerlind N. Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 355-364. DOI: 10.1137/100816833  0.389
2006 Maciel A, Pitassi T. A conditional lower bound for a system of constant-depth proofs with modular connectives Proceedings - Symposium On Logic in Computer Science. 189-198. DOI: 10.1109/LICS.2006.19  0.528
2005 Beame P, Pitassi T, Segerlind N. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity Lecture Notes in Computer Science. 3580: 1176-1188. DOI: 10.1137/060654645  0.376
2005 Bonet ML, Domingo C, Gavaldà R, MacIel A, Pitassi T. Non-automatizability of bounded-depth frege proofs Computational Complexity. 13: 47-68. DOI: 10.1007/s00037-004-0183-5  0.381
2003 Buresh-Oppenheim J, Galesi N, Hoory S, Magen A, Pitassi T. Rank bounds and integrality gaps for cutting planes procedures Annual Symposium On Foundations of Computer Science - Proceedings. 318-326. DOI: 10.1109/SFCS.2003.1238206  0.38
2002 Buresh-Oppenheim J, Beame P, Pitassi T, Raz R, Sabharwal A. Bounded-depth Frege lower bounds for weaker pigeonhole principles Annual Symposium On Foundations of Computer Science - Proceedings. 583-592. DOI: 10.1137/S0097539703433146  0.477
2002 Maciel A, Pitassi T, Woods AR. A new proof of the weak pigeonhole principle Journal of Computer and System Sciences. 64: 843-872. DOI: 10.1006/jcss.2002.1830  0.382
2001 Agrawal M, Allender E, Impagliazzo R, Pitassi T, Rudich S. Reducing the complexity of reductions Computational Complexity. 10: 117-138. DOI: 10.1007/S00037-001-8191-1  0.355
2001 Buss S, Grigoriev D, Impagliazzo R, Pitassi T. Linear gaps between degrees for the polynomial calculus modulo distinct primes Journal of Computer and System Sciences. 62: 267-289. DOI: 10.1006/jcss.2000.1726  0.319
2001 Pitassi T, Raz R. Regular resolution lower bounds for the weak Pigeonhole principle Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 347-355.  0.323
2000 Bonet ML, Pitassi T, Raz R. On interpolation and automatization for Frege systems Siam Journal On Computing. 29: 1939-1967. DOI: 10.1137/S0097539798353230  0.411
2000 Maciel A, Pitassi T, Woods AR. New proof of the weak pigeonhole principle Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 368-377.  0.369
1998 Beame P, Impagliazzo R, Pitassi T. Improved depth lower bounds for small distance connectivity Computational Complexity. 7: 325-345. DOI: 10.1007/S000370050014  0.321
1998 Buss SR, Pitassi T. Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle Journal of Computer and System Sciences. 57: 162-171. DOI: 10.1006/Jcss.1998.1585  0.379
1998 Alekhnovich M, Buss S, Moran S, Pitassi T. Minimum propositional proof length is NP-hard to linearly approximate Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1450: 176-184.  0.314
1997 Bonet M, Pitassi T, Raz R. Lower bounds for cutting planes proofs with small coefficients Journal of Symbolic Logic. 62: 708-728.  0.371
1996 Beame P, Impagliazzo R, Krajíček J, Pitassi T, Pudlák P. Lower bounds on Hilbert's Nullstellensatz and propositional proofs Proceedings of the London Mathematical Society. 73: 1-26. DOI: 10.1112/Plms/S3-73.1.1  0.324
1996 Beame P, Pitassi T. An exponential separation between the parity principle and the pigeonhole principle Annals of Pure and Applied Logic. 80: 195-228. DOI: 10.1016/0168-0072(96)83747-X  0.399
1995 Iwama K, Pitassi T. Exponential lower bounds for the tree-like Hajós calculus Information Processing Letters. 54: 289-294. DOI: 10.1016/0020-0190(95)00035-B  0.403
1993 Pitassi T, Beame P, Impagliazzo R. Exponential lower bounds for the pigeonhole principle Computational Complexity. 3: 97-140. DOI: 10.1007/Bf01200117  0.494
1990 Cook S, Pitassi T. A feasibly constructive lower bound for resolution proofs Information Processing Letters. 34: 81-85. DOI: 10.1016/0020-0190(90)90141-J  0.358
Show low-probability matches.