Publications

  1. Lifting Nullstellensatz to Monotone Span Programs over any Field., Pitassi, T., Robere, R. Proceedings Symposium on Theory of Computing (STOC) 2018.
  2. Learning Adversarially Fair and Transferrable Representations., Madras, D., Creager, E., Pitassi, T., Zemel, R. Proceedings International Conference on Machine Learning, 2018.
  3. Circuit Complexity, Proof Complexity and Polynomial Identity Testing., Grochow, J., Pitassi, T. Journal of the ACM, Accepted.
  4. Hardness of Function Composition for Semantic Read-once Branching Programs, Edmonds, J., Medabalimi, V., Pitassi, T. Proceedings Conference on Computational Complexity (CCC), 2018.
  5. Stabbing Planes, Beame, P., Fleming, N., Impagliazzo, R., Kolokolova, A., Pankratov, D., Pitassi, T., Robere, R. Proceedings Innovations in Theoretical Computer Science (ITCS), 2018.
  6. Strongly Exponential Lower Bounds for Monotone Computation, Pitassi, T., Robere, R. Proceedings Symposium on Theory of Computing (STOC), 2017.
  7. Random CNFs are Hard for Cutting Planes, Fleming, N., Pankratov, D., Pitassi, T., Robere, R. Proceedings Foundations of Computer Science (FOCS), 2017.
  8. Exponential Lower Bounds for Monotone Span Programs, Robere, R., Pitassi, T., Rossman, B., Cook, S. Proceedings Foundations of Computer Science (FOCS), 2016.
  9. Polylogarithmic Frege Depth Lower Bounds via an Expander Switching Lemma, Pitassi, T., Rossman, B, Tan, L., Servedio, R. Proceedings Symposium on Theory of Computing (STOC), 2016.
  10. Algebraic Proof Complexity: Progress, Frontiers and Challenges, Pitassi, T., Tzameret. ACM SIGLOG News, 3(3) pp.21-43, 2016.
  11. Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs, Cook, S., Edmonds, J., Medabalimi, V., Pitassi, T. Proceedings ICALP, 2016.
  12. The Landscape of Communication Complexity Classes, Goos, M., Pitassi, T., Watson, T. Proceedings ICALP, 2016.
  13. The reusable holdout: Preserving validity in adaptive data analysis, Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A. Science, 2015.
  14. Upper and Lower Bounds on the Power of Advice, Chattopadhyay, A., Edmonds, J., Ellen, F., Pitassi, T. Siam Journal on Computing, 2016.
  15. Guilt Free Data Reuse, Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A. Proceedings CACM, 2016.
  16. Preserving Statistical Validity in Adaptive Data Reuse, Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A. Proceedings Symposium on Theory of Computing (STOC), 2015. Journal version in Siam Journal on Computing, to appear.
  17. Deterministic Communication Complexity versus Partition Number, Goos, M., Pitassi, T., Watson, T. Proceedings Foundations of Computer Science (FOCS) 2015. Journal version in SIAM Journal on Computing (Special Issue for selected papers from FOCS 2015) To appear
  18. Communication Lower Bounds via Critical Block Sensitivity, Goos, M., Pitassi, T. SIAM Journal on Computing (Accepted 2018)
  19. Generalization in Adaptive Data Analysis and Holdout Reuse, Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A. Proceedings NIPS, 2015.
  20. Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication Goos, M., Pitassi, T., Watson, T. Proceedings Innovations in Theoretical Computer Science (ITCS), 2015. Journal version in Algorithmica, 2016
  21. The Hardness of Being Private, Ada, A., Chattopadhyay, A., Cook, S., Fontes, L., Koucky, M., Pitassi, T. ACM Transactions on Computation Theory (TOCT), 6(1),2014.
  22. Inapproximability of Treewidth and Related Problems, Wu, Y., Austrin, P., Pitassi, T., Liu, D. Journal of Artificial Intelligence Research, Volume 49, pp. 569-600, 2014.
  23. Bounded-depth Frege Lower Bounds Imply Frege Lower Bounds, Filmus, Y., Pitassi, T., Santhanam, R. ACM Transactions on Computation Theory (TOCT), Vol 7, Issue 2, May 2015.
  24. Exponential Lower bounds and Integrality Gaps for Tree-like Matrix Cut Systems, Pitassi, T., and Segerlind, N. To appear in SIAM Journal of Computing.
    (Preliminary version in SODA, 2009)
  25. The Hardness of Being Private, Ada, A., Chattopadhyay, A., Cook, S., Fontes, L., Koucky, M., and Pitassi, T. Proceedings CCC, 2012.
  26. Inapproximability of Tree-width and Related Graph Layout Problems, Austrin, P., Pitassi, T., and Yu, W. Proceedings APPROX, 2012.
  27. A Little Advice Can Be Very Helpful, Chattopadhyay, A., Edmonds, J., Ellen, F., and Pitassi, T. Proceedings SODA, 2012.
  28. Fairness through Awareness, Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Proceedings ICS, 2012.
  29. Toward a Model for Backtracking and Dynamic Programming, Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A., and Pitassi, T. SIAM Journal of Computing, 2011.
    (Preliminary version in Proceedings CCC, 2005)
  30. Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds, Filmus, Y., Pitassi, T., and Santhanam, R. Proceedings ICALP, 2011.
  31. Automatizability and Simple Stochastic Games, Huang, L. and Pitassi, T. Proceedings ICALP, 2011.
  32. The Story of Set Disjointness, Chattopadhyay, A. and Pitassi, T. SIGACT News Complexity Theory Column, Volume 41, Number 3, 2010.
  33. The PSPACE-Completeness of Black-White Pebbling, Hertel, P. and Pitassi, T. SIAM Journal of Computing Special Issue on Foundations of Computer Science, Volume 39, 2010.
    (Preliminary version in FOCS 2007)
  34. Separating Deterministic from Randomized Multiparty Communication Complexity, Beame, P., David, M., Pitassi, T., and Woelfel, P. Theory of Computing, Volume 6, 2010.
    (Preliminary version in Proceedings ICALP, 2007)
  35. Memoization and DPLL: Formula Caching Proof Systems, Beame, P., Impagliazzo, R., Pitassi, T., and Segerlind, N. ACM Transactions on Computation Theory (TOCT), Volume 1, Issue 3, March 2010.
    (Preliminary version in Proceedings CCC, 2003)
  36. Integrality Gaps of 2 - 0(1) for Vertex Cover SDPs in the Lovasz-Schrijver Hierarchy, Georgiou, K., Magen, A., Pitassi, T., and Tourlakis, I. SIAM Journal of Computing, Volume 39, Number 8, 2010.
    (Preliminary version in Proceedings IEEE FOCS, 2007)
  37. The Limits of Two-Party Differential Privacy, McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., and Vadhan, S. Proceedings IEEE FOCS, 2010.
  38. Differential Privacy under Continual Observation, Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. Proceedings ACM STOC, 2010.
  39. Hardness Amplification in Proof Complexity, Beame, P., Ngoc, T., and Pitassi, T. Proceedings ACM STOC, 2010.
  40. Pan-Private Streaming Algorithms, Dwork, C., M. Naor, T. Pitassi, G. Rothblum, and Yekhanin, S. ICS, 2010.
  41. Effectively Polynomial Simulations, Pitassi, T., and Santhanam, R. ICS, 2010.
  42. Improved Separations between Nondeterministic and Randomized Multiparty Communication, David, M., and Pitassi, T., and Viola, E. ACM Transactions on Computation Theory (TOCT), Volume 1, Issue 2, September 2009.
    (Preliminary version in Proceedings RANDOM, 2008)
  43. Clause Learning Can Effectively Psimulate General Resolution, Bacchus, F., Hertel, P., Pitassi, T., and Van Gelder, A. Proceedings AAAI, 2008.
  44. A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness, Beame, P., Pitassi, T., Segerlind, N., and Wigderson, A. Computational Complexity, 2006.
    (Preliminary version in Proceedings IEEE CCC, 2005)
  45. New Monotone Formulas for the Majority Function, Hoory, S., Magen, A., and Pitassi, T. Proceedings RANDOM, 2006.
  46. On the Complexity of Finding Minimal Representations of Boolean Functions, Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., and Saks, M. Proceedings CCC, 2006.
  47. Lower bounds on constant-depth Frege proofs with mod connectives modulo a hardness conjecture, Maciel, A., and Pitassi, T. Proceedings from LICS, 2006.
  48. 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.
    (Preliminary version in Proceedings FOCS, 2003)
  49. Lower Bounds for Lovasz-Schriver systems and beyond follow from multiparty communication complexity, Beame, P., Pitassi, T., and Segerlind, N. Proceedings 32nd ICALP, 2005.
  50. Lower Bounds for Weaker Pigeonhole Principles, Buresh-Oppenheim, J., Pitassi, T., Raz, R., and Sabharwal, A. SIAM Journal on Computing, Volume 34, 2004.
    (Preliminary version in Proceedings FOCS, 2002)
  51. 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.
  52. Learnability and Automatizability, Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A., and Pitassi, T. Proceedings of FOCS 2004.
  53. "Recursion," Brecht, T., McIlraith, S., and Pitassi, T. Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley Publishing, in press.
  54. DPLL with caching: A new algorithm for #SAT and Bayesian Inference, Bacchus, F., Dalmao, S., and Pitassi, T. Proceedings of UAI, 2003.
  55. Stochastic Satisfiability, Littman, M., Majercik, S., and Pitassi, T. Journal of Automated Reasoning, special issue on satisfiability, in press, 2003.
  56. 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)
  57. The complexity of resolution refinements, Buresh-Oppenheim, J. and Pitassi, T. LICS, 2003.
  58. 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)
  59. 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)
  60. 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)
  61. Linear and negative resolution are weaker than resolution, Buresh-Oppenheim, J., Mitchell, D., and Pitassi, T. ECCC TR01-074, 2002.
  62. A New Proof of the Weak Pigeonhole Principle, Maciel, A., Pitassi, T., and Woods, A. Journal of Computer Systems Sciences, Volume 64, 2002.
    (Preliminary version in Proceedings of ACM STOC, 2000)
  63. An Exponential Separation between Regular and General Resolution, Aleknovich, A., Johannsen, J., Pitassi, T., and Urquhart, A. Proceedings of ACM STOC, 2002.
  64. The efficiency of resolution and Davis-Putnam Procedures, Beame, P., Karp, R., Pitassi, T., and Saks, M. SIAM Journal of Computing, Volume 31, 2002.
    (Preliminary version in Proceedings ACM STOC, 1998)
  65. Minimal propositional proof length is NP-hard to linearly approximate, Aleknovich, A., Buss, S., Moran, S., and Pitassi, T. Journal of Symbolic Logic, Volume 66, 2001.
  66. A gradient-based boosting algorithm for regression problems, Zemel, R., and Pitassi, T. NIPS-13: Advances in Neural Information Processing Systems 13, 2001.
  67. The complexity of Analytic Tableaux, Arai, N., Pitassi, T., and Urquhart, A. Proceedings of ACM Symposium on the Theory of Computing, 2001.
  68. Propositional proof complexity: Past, Present and Future, Beame, P., and Pitassi, T. In G. Paun, G. Rozenberg, and A. Salomaa, eds. Current Trends in Theoretical Computer Science Entering the 21st Century, pp.42-70. World Scientific Publishing, 2001.
    (Preliminary version in The Computational Complexity Column, in the Bulletin of the EATCS, 2000. Also appeared as TR98-067 in ECCC.)
  69. 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)
  70. 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.)
  71. 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)
  72. "Computability," Pitassi, T., McIlraith, S., and Brecht, T. Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley Publishing, 3, pp.612-618, 1999.
  73. Resolution and the weak pigeonhole principle, Buss, S., and Pitassi, T. Springer-Verlag Lecture Notes in Computer Science 1414, 1998. (Publications of selected papers presented at Proceedings from Computer Science Logic '97.)
  74. 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)
  75. 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)
  76. 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, Volume 39, 1998.
  77. Propositional proof complexity and unsolvability of polynomial equations, Pitassi, T. Proceedings of International Congress of Mathematicians Meeting, Berlin, 1998.
  78. 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)
  79. On ACC0[pk]-Frege systems, Maciel, A. and Pitassi, T. Proceedings from ACM Symposium on the Theory of Computing 1997.
  80. Lower bounds for Cutting Planes proofs with small coefficients, Bonet, M., Pitassi, T. and Raz, R. Journal of Symbolic Logic, Volume 62, No. 3, pp. 708-728, 1997.
    (Preliminary version in Proceedings of ACM STOC, 1995)
  81. 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.
  82. An exponential separation between the parity principle and the pigeonhole principle, Beame, P., and Pitassi, T. Annals of Pure and Applied Logic, Volume 80, pp. 197-225, 1996.
    (Preliminary version in Proceedings of LICS, 1993)
  83. Simplified and improved Resolution lower bounds, Beame, P., and Pitassi, T. Proceedings from IEEE Foundations of Computer Science, pp. 274-282, 1996.
  84. Lower bounds for Hilbert's Nullstellensatz and propositional proofs, Beame, P., Krajicek, J., Impagliazzo, R., Pitassi, T. and Pudlak, P. Proceedings of the London Math Society, Volume 73, No. 3, pp. 1-26, 1996.
    (Preliminary version in Proceedings of FOCS, 1994)
  85. Exponential lower bounds for the tree-like Hajos Calculus, Iwama, K. and Pitassi, T. Information Processing Letters, Volume 54, 1995.
  86. 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)
  87. Exponential lower bounds for the pigeonhole principle, Pitassi, T., Beame, P., and Impagliazzo, R. Computational Complexity, Volume 3, No. 2, pp. 97-140, 1994.
  88. Are there hard examples for Frege systems? Bonet, M., Buss, S., and Pitassi, T. Feasible Mathematics, Volume II, Birkhauser, pp. 30-56, 1994.
  89. Upper and lower bounds for tree-like cutting planes proofs, Impagliazzo, R., Pitassi, T., and Urquhart, A. Proceedings from Logic in Computer Science, 1994.
  90. Semantics for nondeterministic asynchronous broadcast networks, Shyamasundar, R. K., Narayana, K.T., and Pitassi, T. Information and Computation, 104, pp. 215-252, 1993.
  91. Approximation and small-depth Frege proofs, Bellantoni, S., Pitassi, T., and Urquhart, A. SIAM Journal on Computing, Volume 21, No. 6, pp. 1161-1179, 1992.
    (Preliminary version in Proceedings of Conference on Structure in Complexity Theory, 1991.)
  92. The complexity of the perfect matching principle, Pitassi, T. and Beame, P. Proceedings of the Seventh Annual Graduate Conference in Computer Science, 1992.
  93. The complexity of Weak Formal Systems, Pitassi, T., Ph.D. thesis, University of Toronto, 1992.
  94. Exponential lower bounds for the pigeonhole principle, Beame, P., Impagliazzo, R., Krajicek, J., Pitassi, T., Pudlak, P., and Woods, A. Proceedings from ACM Symposium on the Theory of Computing, pp. 200-220, 1992.
  95. 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.
  96. A feasibly constructive lower bound for parity, Pitassi, T. Manuscript, 1990.
  97. A feasibly constructive lower bound for Resolution proofs, Cook, S. and Pitassi, T. Information Processing Letters, Volume 34, pp. 81-85, 1990.
  98. A feasibly constructive proof of Fermat's last theorem for n=3, Pitassi, T., Manuscript, 1989.
  99. An expert system for ring-based fault diagnosis, Pitassi, T., Technical Memoranda, AT&T Bell Laboratories, June, 1987.
  100. Semantics for nondeterministic asynchronous broadcast networks, Narayana, K. T., Pitassi, T., and Shyamasundar, R.K., Lecture Notes in Computer Science 267 pp. 72-83, 1987. Proceedings of the 1987 International Conference on Automata, Languages and Programming.
  101. 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)