Toniann Pitassi

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook: Average Case Lower Bounds for Monotone Switching Networks. Electronic Colloquium on Computational Complexity (ECCC) 20: 54 (2013)

Toniann Pitassi, Nathan Segerlind: Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. SIAM J. Comput. 41(1): 128-159 (2012)

Per Austrin, Toniann Pitassi, Yu Wu: Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. APPROX-RANDOM 2012: 13-24

Toniann Pitassi: Communication Complexity and Information Complexity: Foundations and New Directions. IEEE Conference on Computational Complexity 2012: 136

Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi: The Hardness of Being Private. IEEE Conference on Computational Complexity 2012: 192-202

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel: Fairness through awareness. ITCS 2012: 214-226

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi: A little advice can be very helpful. SODA 2012: 615-625

Howard J. Karloff, Toniann Pitassi (Eds.): Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. ACM 2012, isbn 978-1-4503-1245-5

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi: Value Elimination: Bayesian Inference via Backtracking Search. CoRR abs/1212.2452 (2012)

Allan Borodin, Toniann Pitassi, Alexander A. Razborov: Special Issue In Memory of Misha Alekhnovich. Foreword. Computational Complexity 20(4): 579-590 (2011)

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. Computational Complexity 20(4): 679-740 (2011)

Lei Huang, Toniann Pitassi: Automatizability and Simple Stochastic Games. ICALP (1) 2011: 605-617

Yuval Filmus, Toniann Pitassi, Rahul Santhanam: Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds. ICALP (1) 2011: 618-629

Toniann Pitassi: Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results. LICS 2011: 119

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel: Fairness Through Awareness. CoRR abs/1104.3913 (2011)

Per Austrin, Toniann Pitassi, Yu Wu: Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. CoRR abs/1109.4910 (2011)

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan: The Limits of Two-Party Differential Privacy. Electronic Colloquium on Computational Complexity (ECCC) 18: 106 (2011)

Philipp Hertel, Toniann Pitassi: The PSPACE-Completeness of Black-White Pebbling. SIAM J. Comput. 39(6): 2622-2682 (2010)

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis: Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy. SIAM J. Comput. 39(8): 3553-3570 (2010)

Arkadev Chattopadhyay, Toniann Pitassi: The story of set disjointness. SIGACT News 41(3): 59-85 (2010)

Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel: Separating Deterministic from Randomized Multiparty Communication Complexity. Theory of Computing 6(1): 201-225 (2010)

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. TOCT 1(3) (2010)

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan: The Limits of Two-Party Differential Privacy. FOCS 2010: 81-90

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, Sergey Yekhanin: Pan-Private Streaming Algorithms. ICS 2010: 66-80

Toniann Pitassi, Rahul Santhanam: Effectively Polynomial Simulations. ICS 2010: 370-382

Paul Beame, Trinh Huynh, Toniann Pitassi: Hardness amplification in proof complexity. STOC 2010: 87-96

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum: Differential privacy under continual observation. STOC 2010: 715-724

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi: Solving #SAT and Bayesian Inference with Backtracking Search. J. Artif. Intell. Res. (JAIR) 34: 391-442 (2009)

Matei David, Toniann Pitassi, Emanuele Viola: Improved Separations between Nondeterministic and Randomized Multiparty Communication. TOCT 1(2) (2009)

Toniann Pitassi, Nathan Segerlind: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. SODA 2009: 355-364

Paul Beame, Trinh Huynh, Toniann Pitassi: Hardness Amplification in Proof Complexity. CoRR abs/0912.0568 (2009)

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi: The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. 74(1): 16-34 (2008)

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks: Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table. SIAM J. Comput. 38(1): 63-84 (2008)

Philipp Hertel, Fahiem Bacchus, Toniann Pitassi, Allen Van Gelder: Clause Learning Can Effectively P-Simulate General Propositional Resolution. AAAI 2008: 283-290

Matei David, Toniann Pitassi, Emanuele Viola: Improved Separations between Nondeterministic and Randomized Multiparty Communication. APPROX-RANDOM 2008: 371-384

Matei David, Toniann Pitassi: Separating NOF communication complexity classes RP and NP. CoRR abs/0802.3860 (2008)

Matei David, Toniann Pitassi: Separating NOF communication complexity classes RP and NP. Electronic Colloquium on Computational Complexity (ECCC) 15(014) (2008)

Joshua Buresh-Oppenheim, Toniann Pitassi: The complexity of resolution refinements. J. Symb. Log. 72(4): 1336-1352 (2007)

Paul Beame, Toniann Pitassi, Nathan Segerlind: Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. SIAM J. Comput. 37(3): 845-869 (2007)

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An Exponential Separation between Regular and General Resolution. Theory of Computing 3(1): 81-102 (2007)

Philipp Hertel, Toniann Pitassi: Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. FOCS 2007: 137-149

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis: Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy. FOCS 2007: 702-712

Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel: Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. ICALP 2007: 134-145

Philipp Hertel, Toniann Pitassi: Black-White Pebbling is PSPACE-Complete. Electronic Colloquium on Computational Complexity (ECCC) 14(044) (2007)

Philipp Hertel, Toniann Pitassi: An Exponential Time/Space Speedup For Resolution. Electronic Colloquium on Computational Complexity (ECCC) 14(046) (2007)

Nathan Segerlind, Toniann Pitassi: Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. Electronic Colloquium on Computational Complexity (ECCC) 14(107) (2007)

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson: A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Computational Complexity 15(4): 391-432 (2006)

Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart: The complexity of analytic tableaux. J. Symb. Log. 71(3): 777-790 (2006)

Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi: Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing 2(1): 65-90 (2006)

Shlomo Hoory, Avner Magen, Toniann Pitassi: Monotone Circuits for the Majority Function. APPROX-RANDOM 2006: 410-425

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks: Minimizing DNF Formulas and AC⁰_d Circuits Given a Truth Table. IEEE Conference on Computational Complexity 2006: 237-251

Alexis Maciel, Toniann Pitassi: Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives. LICS 2006: 189-200

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Formula Caching in DPLL. Electronic Colloquium on Computational Complexity (ECCC) 13(140) (2006)

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis: Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 13(152) (2006)

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson: A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. IEEE Conference on Computational Complexity 2005: 52-66

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. IEEE Conference on Computational Complexity 2005: 308-322

Paul Beame, Toniann Pitassi, Nathan Segerlind: Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP 2005: 1176-1188

Paul Beame, Toniann Pitassi, Nathan Segerlind: Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity. Electronic Colloquium on Computational Complexity (ECCC)(053) (2005)

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks: Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electronic Colloquium on Computational Complexity (ECCC)(126) (2005)

Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi: Non-Automatizability of Bounded-Depth Frege Proofs. Computational Complexity 13(1-2): 47-68 (2004)

Toniann Pitassi, Ran Raz: Regular Resolution Lower Bounds For The Weak Pigeonhole Principle. Combinatorica 24(3): 503-524 (2004)

Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal: Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. SIAM J. Comput. 34(2): 261-276 (2004)

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi: Learnability and Automatizability. FOCS 2004: 621-630

Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi: Combining Component Caching and Clause Learning for Effective Model Counting. SAT 2004

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind: Memoization and DPLL: Formula Caching Proof Systems. IEEE Conference on Computational Complexity 2003: 248-

Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi: Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. FOCS 2003: 318-327

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi: Algorithms and Complexity Results for #SAT and Bayesian Inference. FOCS 2003: 340-351

Josh Buresh-Oppenheim, Toniann Pitassi: The Complexity of Resolution Refinements. LICS 2003: 138-

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi: Value Elimination: Bayesian Interence via Backtracking Search. UAI 2003: 20-28

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi: DPLL with Caching: A new algorithm for #SAT and Bayesian Inference. Electronic Colloquium on Computational Complexity (ECCC) 10(003) (2003)

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi: Homogenization and the polynomial calculus. Computational Complexity 11(3-4): 91-108 (2002)

Alexis Maciel, Toniann Pitassi, Alan R. Woods: A New Proof of the Weak Pigeonhole Principle. J. Comput. Syst. Sci. 64(4): 843-872 (2002)

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. 31(4): 1048-1075 (2002)

Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal: Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS 2002: 583-592

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An exponential separation between regular and general resolution. STOC 2002: 448-456

Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal: Bounded-depth Frege lower bounds for weaker pigeonhole principles. Electronic Colloquium on Computational Complexity (ECCC)(023) (2002)

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the complexity of reductions. Computational Complexity 10(2): 117-138 (2001)

Michael L. Littman, Stephen M. Majercik, Toniann Pitassi: Stochastic Boolean Satisfiability. J. Autom. Reasoning 27(3): 251-296 (2001)

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62(2): 267-289 (2001)

Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi: Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. J. Symb. Log. 66(1): 171-191 (2001)

Paul Beame, Toniann Pitassi: Propositional Proof Complexity: Past, Present, and Future. Current Trends in Theoretical Computer Science 2001: 42-70

Toniann Pitassi, Ran Raz: Regular resolution lower bounds for the weak pigeonhole principle. STOC 2001: 347-355

Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart: The complexity of analytic tableaux. STOC 2001: 356-363

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An Exponential Separation between Regular and General Resolution. Electronic Colloquium on Computational Complexity (ECCC) 8(056) (2001)

Josh Buresh-Oppenheim, David G. Mitchell, Toniann Pitassi: Linear and Negative Resolution are Weaker than Resolution. Electronic Colloquium on Computational Complexity (ECCC) 8(074) (2001)

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: On Interpolation and Automatization for Frege Systems. SIAM J. Comput. 29(6): 1939-1967 (2000)

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi: Homogenization and the Polynominal Calculus. ICALP 2000: 926-937

Richard S. Zemel, Toniann Pitassi: A Gradient-Based Boosting Algorithm for Regression Problems. NIPS 2000: 696-702

Alexis Maciel, Toniann Pitassi, Alan R. Woods: A new proof of the weak pigeonhole principle. STOC 2000: 368-377

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). IEEE Conference on Computational Complexity 1999: 5

Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi: Non-Automatizability of Bounded-Depth Frege Proofs. IEEE Conference on Computational Complexity 1999: 15-23

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556

Paul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Bounds for Small Distance Connectivity. Computational Complexity 7(4): 325-345 (1998)

Paul Beame, Toniann Pitassi: Propositional Proof Complexity: Past, Present and Future. Bulletin of the EATCS 65: 66-89 (1998)

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The Relative Complexity of NP Search Problems. J. Comput. Syst. Sci. 57(1): 3-19 (1998)

Samuel R. Buss, Toniann Pitassi: Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. J. Comput. Syst. Sci. 57(2): 162-171 (1998)

Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi: Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS 1998: 176-184

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas. STOC 1998: 561-571

Paul Beame, Toniann Pitassi: Propositional Proof Complexity: Past, Present and Future. Electronic Colloquium on Computational Complexity (ECCC) 5(67) (1998)

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: Lower Bounds for Cutting Planes Proofs with Small Coefficients. J. Symb. Log. 62(3): 708-728 (1997)

Samuel R. Buss, Toniann Pitassi: Resolution and the Weak Pigeonhole Principle. CSL 1997: 149-156

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: No Feasible Interpolation for TC0-Frege Proofs. FOCS 1997: 254-263

Alexis Maciel, Toniann Pitassi: On ACC⁰[p^k] Frege Proofs. STOC 1997: 720-729

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich: Reducing the Complexity of Reductions. STOC 1997: 730-738

Paul Beame, Toniann Pitassi: An Exponential Separation Between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Logic 80(3): 195-228 (1996)

Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich: The future of computational complexity theory: part II. SIGACT News 27(4): 3-7 (1996)

Samuel R. Buss, Toniann Pitassi: Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. IEEE Conference on Computational Complexity 1996: 233-242

Toniann Pitassi: Algebraic Propositional Proof Systems. Descriptive Complexity and Finite Models 1996: 215-244

Paul Beame, Toniann Pitassi: Simplified and Improved Resolution Lower Bounds. FOCS 1996: 274-282

Kazuo Iwama, Toniann Pitassi: Exponential Lower Bounds for the Tree-Like Hajós Calculus. Inf. Process. Lett. 54(5): 289-294 (1995)

Toniann Pitassi, Alasdair Urquhart: The Complexity of the Hajos Calculus. SIAM J. Discrete Math. 8(3): 464-483 (1995)

Paul Beame, Russell Impagliazzo, Toniann Pitassi: Improved Depth Lower Vounds for Small Distance Connectivity. FOCS 1995: 692-701

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi: The relative complexity of NP search problems. STOC 1995: 303-314

Maria Luisa Bonet, Toniann Pitassi, Ran Raz: Lower bounds for cutting planes proofs with small coefficients. STOC 1995: 575-584

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák: Lower Bound on Hilbert's Nullstellensatz and propositional proofs. FOCS 1994: 794-806

Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart: Upper and Lower Bounds for Tree-Like Cutting Planes Proofs. LICS 1994: 220-228

Toniann Pitassi, Paul Beame, Russell Impagliazzo: Exponential Lower Bounds for the Pigeonhole Principle. Computational Complexity 3: 97-140 (1993)

R. K. Shyamasundar, K. T. Narayana, Toniann Pitassi: Semantics of Nondeterministic Asynchronous Broadcast Networks. Inf. Comput. 104(2): 215-252 (1993)

Paul Beame, Toniann Pitassi: An Exponential Separation between the Matching Principle and the Pigeonhole Principle. LICS 1993: 308-319

Stephen Bellantoni, Toniann Pitassi, Alasdair Urquhart: Approximation and Small-Depth Frege Proofs. SIAM J. Comput. 21(6): 1161-1179 (1992)

Toniann Pitassi, Alasdair Urquhart: The Complexity of the Hajós Calculus. FOCS 1992: 187-196

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods: Exponential Lower Bounds for the Pigeonhole Principle. STOC 1992: 200-220

Stephen Bellantoni, Toniann Pitassi, Alasdair Urquhart: Approximation and Small Depth Frege Proofs. Structure in Complexity Theory Conference 1991: 367-390

Stephen A. Cook, Toniann Pitassi: A Feasibly Constructive Lower Bound for Resolution Proofs. Inf. Process. Lett. 34(2): 81-85 (1990)

R. K. Shyamasundar, K. T. Narayana, Toniann Pitassi: Semantics for Nondeterministic Asynchronous Broadcast Networks. ICALP 1987: 72-83