Publications

  1. Pan-Private Streaming Algorithms, C. Dwork, M. Naor, T. Pitassi, G. Rothblum, and S. Yekhanin, ICS, 2010.  


    2.  

  2. Effectively Polynomial Simulations, Pitassi, T., and Santhanam, R., ICS, 2010.  


    3.  

  3. Exponential Lower Bounds and Integrality Gaps for Tree-like Lovasz-Schrijver Procedures, Pitassi, T., and Segerlind, N., SODA, 2009.  


    4.  

  4. Clause Learning Can Effectively Psimulate General Resolution, Bacchus, F., Hertel, P., Pitassi, T., and Van Gelder, A., AAAI, 2008.  


    5.  

  5. Improved Separations between Randomized and Nondeterministic Multiparty Communication Complexity, Matei, D., and Pitassi, T., and Viola, E., RANDOM, 2008.  


    6.  

  6. Exponential Time-Space Tradeoffs for Resolution and the PSPACE Completeness of Black-White Pebbling, Hertel, P., and Pitassi, T., Proceedings FOCS , 2007. 


    7.  

  7. Tight Integrality Gaps for Vertex Cover SDPs in the Lovasz-Schrijver Hierarchy, Konstantinos, G., Magen, A., Pitassi, T., and Tourlakis, I., Proceedings FOCS , 2007. 


    8.  

  8. Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity, Beame, P., David, M., Pitassi, T., and Woelfel, P., Proceedings ICALP , 2007. 


    9.  

  9. A Direct Sum Theorem for Corruption and a Lower Bound for the Multiparty Communication Complexity of Set Disjointness, Beame, P., Pitassi, T., Segerlind, N., and Wigderson, A., Journal on Computational Complexity, 2006. 


    10.  

  10. New Monotone Formulas for the Majority Function, Hoory, S., Magen, A., and Pitassi, T., Proceedings from RANDOM, 2006. 


    11.  

  11. On the Complexity of Finding Minimal Representations of Boolean Functions, Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., and Saks, M., Proceedings from CCC, 2006. 


    12.  

  12. Lower bounds on constant-depth Frege proofs with mod connectives modulo a hardness conjecture, Maciel, A., and Pitassi, T., Proceedings from LICS, 2006. 


    13.  

  13. Rank Bounds and Integrality Gaps for Cutting Planes Procedures, Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., and Pitassi, T., Journal of Theory of Computing, 2006. 


    14.  

  14. Lower Bounds for Lovasz-Schriver systems and beyond follow from multiparty communication complexity, Beame, P., Pitassi, T., and Segerlind, N., Proceedings from 32nd ICALP, 2005. 


    15.  

  15. Lower Bounds for Weaker Pigeonhole Principles, Buresh-Oppenheim, J., Pitassi, T., Raz, R., and Sabharwal, A., SIAM Journal on Computing, Volume 34, 2005. 


    16.  

  16. Combining Component Caching and Clause Learning for Effective Model Counting, Sang, T., Bacchus, T., Beame, P., Kautz, H., and Pitassi, T. Proceedings of SAT 2004.  


    17.  

  17. Learnability and Automatizability, Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A., and Pitassi, T., Proceedings of FOCS 2004. 


    18.  

  18. Recursion, Brecht, T., McIlraith, S., and Pitassi, T., Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley Publishing, In press.


    19.  

  19. DPLL with caching: A new algorithm for #SAT and Bayesian Inference, Bacchus, F., Dalmao, S., and Pitassi, T., Proceedings of UAI, 2003. 


    20.  

  20. Stochastic Satisfiability, Littman, M., Majercik, S., and Pitassi, T., Journal of Automated Reasoning, Special issue on Satisfiability, In press, 2003.


    21.  

  21. Homogenization and the Polynomial Calculus, Buresh-Oppenheim, J., Clegg, M., Impagliazzo, R., and Pitassi, T., Journal of Computational Complexity, In press, 2003.  Preliminary version in Proceedings of ICALP, 2000.


    22.  

  22. The complexity of resolution refinements, Buresh-Oppenheim, J., and Pitassi, T., LICS, 2003. 


    23.  

  23. Lower bounds for regular resolution proofs of the weak pigeonhole principle, Pitassi, T., and Raz, R., Combinatorica, In press, 2003. Preliminary version in Proceedings FOCS 2002.


    24.  

  24. No automatization or interpolation for bounded-depth Frege systems, Bonet, M., Domingo, C., Gavalda, R., Maciel, A.,  and Pitassi, T., Journal of Computational Complexity, In press, 2003.  Preliminary version in Proceedings of Conference on Complexity Theory, 1999.


    25.  

  25. Memorization and DPLL: Formula Caching Proof Systems, Beame, P., Impagliazzo, R., Pitassi, T., and Segerlind, N.  Proceedings of Computational Complexity, 2003.


    26.  

  26. Bounded-depth Frege lower bounds for weaker pigeonhole principles, Buresh-Oppenheim, J., Beame, P., Pitassi, T., Raz, R., and Sabharwal, A., In Proceedings 43rd Annual Symposium on Foundations of Computer Science.  Also appeared as ECCC TR02-023, 2002. 


    27.  

  27. Linear and negative resolution are weaker than resolution, Bureshop-Oppenheim, J., Mitchell, D., and Pitassi, T., Appeared in ECCC TR01-074, 2002. 


    28.  

  28. A New Proof of the Weak Pigeonhole Principle, Maciel, A., Pitassi, T., and Woods, A., Journal of Computer Systems Sciences, 64, pp.843-872, 2002.  Preliminary version in Proceedings of ACM STOC, 2000.


    29.  

  29. An Exponential Separation between Regular and General Resolution, Aleknovich, A., Johannsen, J., Pitassi, T., and Urquhart, A., Proceedings of ACM Symposium on the Theory of Computing, Montreal, CA, 2002.


    30.  

  30. The efficiency of resolution and Davis-Putnam Procedures, Beame, P., Karp, R., Pitassi, T., and Saks, M., SIAM Journal of Computing, 31 (4), pp. 1048-1075, 2002.  Preliminary version in Proceedings ACM STOC, 1998.


    31.  

  31. Minimal propositional proof length is NP-hard to linearly approximate, Aleknovich, A., Buss, S., Moran, S., and Pitassi, T., Journal of Symbolic Logic, 66, pp. 171-191, 2001.


    32.  

  32. A gradient-based boosting algorithm for regression problems, Zemel, R., and Pitassi, T., NIPS-13: Advances in Neural Information Processing Systems 13, 2001.


    33.  

  33. The complexity of Analytic Tableaux, Arai, N., Pitassi, T., and Urquhart, A., Proceedings of ACM Symposium on the Theory of Computing, 2001. 


    34.  

  34. Propositional proof complexity: Past, Present and Future, Beame, P., and Pitassi, T., In G. Paun, G. Rozenberg, and A. Salomaa, editors. Current Trends in Theoretical Computer Science Entering the 21st Century, pp.42-70. World Scientific Publishing 2001.  Earlier version in The Computational Complexity Column, in the Bulletin of the EATCS, 2000. Also appeared as TR98-067 in ECCC. 


    35.  

  35. Reducing the Complexity of Reductions, Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T., and  Rudich, S., Journal of Computational Complexity, 10, pp.117-138, 2001.  Preliminary version in Proceedings of ACM STOC, 2001. 


    36.  

  36. Linear gaps between degrees for the polynomial calculus modulo distinct primes, Buss, S., Grigoriev, D., Impagliazzo, R., and Pitassi, T., Journal of Computer Systems Sciences, 62, pp. 267-289, 2001.  Preliminary version in Proceedings of ACM STOC, 1999. One page abstract in Proceedings of Computational Complexity, 1999.


    37.  

  37. On interpolation and automatization for Frege systems, Bonet, M., Pitassi, T., and Raz, R., SIAM Journal of Computing,  Vol 29, No. 6, pp. 1939-1967, 2000.  Preliminary version in Proceedings of IEEE FOCS, 1997.


    38.  

  38. Computability, Pitassi, T., McIlraith, S., and Brecht, T., In Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley Publishing, 3, pp.612-618, 1999.


    39.  

  39. Resolution and the weak pigeonhole principle, Buss, S., and Pitassi, T., Springer-Verlag Lecture Notes in Computer Science 1414. (Publications of selected papers presented at Proceedings from Computer Science Logic '97.}), 1998. 


    40.  

  40. Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle, Buss, S., and Pitassi, T., Journal of Computer Systems Sciences, Volume 57, pp. 162-171, 1998.  Preliminary version in Proceedings of Conference on Computational Complexity, 1998.


    41.  

  41. The relative complexity of NP search problems, Beame, P., Cook, S., Edmonds, J., Impagliazzo, R., and Pitassi, T., Journal of Computer Systems Sciences, 57, pp.3-19, 1998.  Preliminary version in Proceedings of ACM STOC, 1995.


    42.  

  42. Towards lower bounds for bounded-depth Frege proofs with modular connectives, Maciel, A., and Pitassi, T., In Proof Complexity and Feasible Arithmetics, American Math. Soc., DIMACS series in Discrete Mathematics and Theoretical Computer Science, Vol. 39, 1998.


    43.  

  43. Propositional proof complexity and unsolvability of polynomial equations, Pitassi, T., Proceedings of International Congress of Mathematicians Meeting}, Berlin, 1998.  


    44.  

  44. Improved depth lower bounds for small distance connectivity, Beame, P., Impagliazzo, R., and Pitassi, T., Computational Complexity, 7, pp. 325-345, 1998.  Preliminary version in Proceedings of IEEE FOCS 1995.


    45.  

  45. On ACC0[pk]-Frege systems, Maciel, A., and Pitassi, T., Proceedings from ACM Symposium on the Theory of Computing, 1997. 


    46.  

  46. Lower bounds for Cutting Planes proofs with small coefficients, Bonet, M., Pitassi, T. and Raz, R., Journal of Symbolic Logic, Vol. 62, No. 3, pp. 708-728, 1997.  Preliminary version in Proceedings of ACM STOC, 1995.


    47.  

  47. Algebraic propositional proof systems, Pitassi, T., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 31, Descriptive Complexity and Finite Models, Immerman and Kolaitis (Eds.), pp. 215-244, 1996.


    48.  

  48. An exponential separation between the parity principle and the pigeonhole principle, Beame, P., and Pitassi, T., Annals of Pure and Applied Logic, Vol. 80,  pp. 197-225, 1996.  Preliminary version in Proceedings of LICS, 1993.   


    49.  

  49. Simplified and improved Resolution lower bounds, Beame, P., and Pitassi, T., Proceedings from IEEE Foundations of Computer Science, pp. 274-282, 1996. 


    50.  

  50. Lower bounds for Hilbert's Nullstellensatz and propositional proofs, Beame, P., Krajicek, J., Impagliazzo, R., Pitassi, T., Pudlak, P., Proceedings of the London Math Society, Vol. 73, No. 3, pp. 1-26, 1996.  Preliminary version in Proceedings of FOCS, 1994.


    51.  

  51. Exponential lower bounds for the tree-like Hajos Calculus, Iwama, K., and Pitassi, T., Information Processing Letters, Vol. 54, pp. 289-294, 1995.


    52.  

  52. The complexity of the Hajos Calculus, Pitassi, T. and Urquhart, A., SIAM Journal on Discrete Mathematics, Volume 8, Issue 3, 1995.  Preliminary version in Proceedings of IEEE FOCS, 1992.


    53.  

  53. Exponential lower bounds for the pigeonhole principle, Pitassi, T., Beame, P., and Impagliazzo, R., Computational Complexity, Vol. 3, No. 2, pp. 97-140, 1994. 


    54.  

  54. Are there hard examples for Frege systems?  Bonet, M., Buss, S., and Pitassi, T., Feasible Mathematics, Volume II, Birkhauser, pp. 30-56, 1994. 


    55.  

  55. Upper and lower bounds for tree-like cutting planes proofs, Impagliazzo, R., Pitassi, T., and Urquhart, A., Proceedings from Logic in Computer Science, 1994. 


    56.  

  56. Semantics of nondeterministic asynchronous broadcast networks, Shyamasundar, R. K., Narayana, K.T., and Pitassi, T., Information and Computation, 104, pp. 215-252, 1993. 


    57.  

  57. Approximation and small-depth Frege proofs, Bellantoni, S., Pitassi, T., and Urquhart, A., SIAM Journal on Computing, Vol. 21, No. 6, pp. 1161-1179, 1992.  Preliminary version in Proceedings of Conference on Structure in Complexity Theory, 1991. 


    58.  

  58. The complexity of the perfect matching principle, Pitassi, T. and Beame, P., Proceedings of the Seventh Annual Graduate Conference in Computer Science, Buffalo, 1992. 


    59.  

  59. The complexity of Weak Formal Systems, Pitassi, T., Ph.D. thesis, University of Toronto, 1992. 


    60.  

  60. Exponential lower bounds for the pigeonhole principle, Beame, P., Impagliazzo, R., Krajicek, J., Pitassi, T., Pudlak, P., Woods, A., Proceedings from ACM Symposium on the Theory of Computing, pp. 200-220, 1992.  


    61.  

  61. Topics in complexity theory: Part I. Expander graphs and connections with complexity, Part II. Borel sets and circuit complexity, Sipser, M., Kapron, B., and Pitassi, T., DCS Technical Report Number 254/91, 1991. 


    62.  

  62. A feasibly constructive lower bound for parity. Manuscript, 1990., Pitassi, T. 


    63.  

  63. A feasibly constructive lower bound for Resolution proofs, Cook, S. A. and Pitassi, T., Information Processing Letters, Volume 34, pp. 81-85, 1990. 


    64.  

  64. A feasibly constructive proof of Fermat's last theorem for n=3, Pitassi, T., Manuscript, 1989. 


    65.  

  65. An expert system for ring-based fault diagnosis, Pitassi, T., Technical Memoranda, AT&T Bell Laboratories, June, 1987. 


    66.  

  66. Semantics for nondeterministic asynchronous broadcast networks,  Narayana, K. T., Pitassi, T., and Shyamasundar, R.K., In Lecture Notes in Computer Science 267 (pp. 72--83), 1987.  Proceedings of the 1987 International Conference on Automata, Languages and Programming. 


    67.  

  67. Denotational semantics for communicating sequential processes with broadcast, Pitassi, T., Master's Thesis.  Also appeared as Technical Report, Department of Computer Science,  The Pennsylvania State University, January, 1985. 


    68.  

 

Toniann Pitassi, toni@cs.toronto.edu