Toniann Pitassi

According to our database, Toniann Pitassi authored at least 175 papers between 1990 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Black-Box PPP is not Turing-Closed.

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2024

2023

An improved protocol for ExactlyN with more than 3 players.

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman

Electron. Colloquium Comput. Complex., 2023

Prompt Risk Control: A Rigorous Framework for Responsible Deployment of Large Language Models.

Thomas P. Zollo, Todd Morrill, Zhun Deng, Jake C. Snell, Toniann Pitassi, Richard S. Zemel

CoRR, 2023

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing.

Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir

CoRR, 2023

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.

Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Distribution-Free Statistical Dispersion Control for Societal Applications.

Zhun Deng, Thomas P. Zollo, Jake Snell, Toniann Pitassi, Richard S. Zemel

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions.

Jake Snell, Thomas P. Zollo, Zhun Deng, Toniann Pitassi, Richard S. Zemel

Proceedings of the Eleventh International Conference on Learning Representations, 2023

On the Algebraic Proof Complexity of Tensor Isomorphism.

Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

J. ACM, 2022

The Strength of Equality Oracles in Communication.

Toniann Pitassi, Morgan Shirley, Adi Shraibman

Electron. Colloquium Comput. Complex., 2022

Lower bounds for Polynomial Calculus with extension variables over finite fields.

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2022

Secret Sharing, Slice Formulas, and Monotone Real Circuits.

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2022

Learning versus Refutation in Noninteractive Local Differential Privacy.

Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi

CoRR, 2022

Reproducibility in learning.

Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

On Learning and Refutation in Noninteractive Local Differential Privacy.

Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Lifting with Sunflowers.

Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Extremely Deep Proofs.

Noah Fleming, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2021

Reflections on Proof Complexity and Counting Principles.

Noah Fleming, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2021

On the Power and Limitations of Branch and Cut.

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

Electron. Colloquium Comput. Complex., 2021

Size and Depth Separation in Approximating Natural Functions with Neural Networks.

Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir

CoRR, 2021

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity.

Toniann Pitassi, Morgan Shirley, Thomas Watson

Comput. Complex., 2021

Theoretical bounds on estimation error for meta-learning.

James Lucas, Mengye Ren, Irene Raissa Kameni, Toniann Pitassi, Richard S. Zemel

Proceedings of the 9th International Conference on Learning Representations, 2021

Algebraic Proof Systems (Invited Talk).

Toniann Pitassi

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tradeoffs for small-depth Frege proofs.

Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Size and Depth Separation in Approximating Benign Functions with Neural Networks.

Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir

Proceedings of the Conference on Learning Theory, 2021

On the Pseudo-Deterministic Query Complexity of NP Search Problems.

Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam

Proceedings of the 36th Computational Complexity Conference, 2021

2020

KRW Composition Theorems via Lifting.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2020

Lifting: As Easy As 1, 2, 3.

Ian Mertz, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2020

Automating Algebraic Proof Systems is NP-Hard.

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende

Electron. Colloquium Comput. Complex., 2020

Automating Cutting Planes is NP-Hard.

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2020

Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers.

Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

Causal Modeling for Fairness In Dynamical Systems.

Elliot Creager, David Madras, Toniann Pitassi, Richard S. Zemel

Proceedings of the 37th International Conference on Machine Learning, 2020

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende

Electron. Colloquium Comput. Complex., 2019

The Surprising Power of Constant Depth Algebraic Proofs.

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2019

Semialgebraic Proofs and Efficient Algorithm Design.

Noah Fleming, Pravesh Kothari, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2019

Query-to-Communication Lifting Using Low-Discrepancy Gadgets.

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2019

Correction to: Query-to-Communication Lifting for P NP.

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Comput. Complex., 2019

Query-to-Communication Lifting for P NP.

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Comput. Complex., 2019

On the Communication Complexity of High-Dimensional Permutations.

Nati Linial, Toniann Pitassi, Adi Shraibman

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Flexibly Fair Representation Learning by Disentanglement.

Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa A. Weis, Kevin Swersky, Toniann Pitassi, Richard S. Zemel

Proceedings of the 36th International Conference on Machine Learning, 2019

Short Proofs Are Hard to Find.

Ian Mertz, Toniann Pitassi, Yuanhao Wei

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Query-To-Communication Lifting for BPP Using Inner Product.

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Progress in Lifting and Applications in Lower Bounds (Invited Talk).

Toniann Pitassi

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Fairness through Causal Awareness: Learning Causal Latent-Variable Models for Biased Data.

David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel

Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

2018

Randomized Communication versus Partition Number.

Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson

ACM Trans. Comput. Theory, 2018

Communication Lower Bounds via Critical Block Sensitivity.

Mika Göös, Toniann Pitassi

SIAM J. Comput., 2018

Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System.

Joshua A. Grochow, Toniann Pitassi

J. ACM, 2018

Fairness Through Causal Awareness: Learning Latent-Variable Models for Biased Data.

David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel

CoRR, 2018

The Landscape of Communication Complexity Classes.

Mika Göös, Toniann Pitassi, Thomas Watson

Comput. Complex., 2018

Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer.

David Madras, Toniann Pitassi, Richard S. Zemel

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Learning Adversarially Fair and Transferable Representations.

David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel

Proceedings of the 35th International Conference on Machine Learning, 2018

Predict Responsibly: Increasing Fairness by Learning to Defer.

David Madras, Toniann Pitassi, Richard S. Zemel

Proceedings of the 6th International Conference on Learning Representations, 2018

Hardness of Function Composition for Semantic Read once Branching Programs.

Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Lifting Nullstellensatz to Monotone Span Programs over Any Field.

Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Query-to-Communication Lifting for BPP.

Mika Göös, Toniann Pitassi, Thomas Watson

Electron. Colloquium Comput. Complex., 2017

Random CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Stabbing Planes.

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Guilt-free data reuse.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

Commun. ACM, 2017

Random Θ(log n)-CNFs Are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Algebraic proof complexity: progress, frontiers and challenges.

Toniann Pitassi, Iddo Tzameret

ACM SIGLOG News, 2016

Upper and Lower Bounds on the Power of Advice.

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi

SIAM J. Comput., 2016

Strongly Exponential Lower Bounds for Monotone Computation.

Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2016

Exponential Lower Bounds for Monotone Span Programs.

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Electron. Colloquium Comput. Complex., 2016

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.

Mika Göös, Toniann Pitassi, Thomas Watson

Algorithmica, 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.

Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs.

Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds.

Yuval Filmus, Toniann Pitassi, Rahul Santhanam

ACM Trans. Comput. Theory, 2015

Deterministic Communication vs. Partition Number.

Mika Göös, Toniann Pitassi, Thomas Watson

Electron. Colloquium Comput. Complex., 2015

Randomized Communication vs. Partition Number.

Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson

Electron. Colloquium Comput. Complex., 2015

Preserving Statistical Validity in Adaptive Data Analysis.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Generalization in Adaptive Data Analysis and Holdout Reuse.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Inapproximability of Treewidth and Related Problems (Extended Abstract).

Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014

The Hardness of Being Private.

Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi

ACM Trans. Comput. Theory, 2014

Inapproximability of Treewidth and Related Problems.

Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu

J. Artif. Intell. Res., 2014

Circuit complexity, proof complexity, and polynomial identity testing.

Joshua A. Grochow, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2014

Lifting lower bounds for tree-like proofs.

Alexis Maciel, Phuong Nguyen, Toniann Pitassi

Comput. Complex., 2014

2013

Average Case Lower Bounds for Monotone Switching Networks.

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

Electron. Colloquium Comput. Complex., 2013

Tight Bounds for Set Disjointness in the Message Passing Model

Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan

CoRR, 2013

On the Expressive Power of Restricted Boltzmann Machines.

James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard S. Zemel

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Learning Fair Representations.

Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, Cynthia Dwork

Proceedings of the 30th International Conference on Machine Learning, 2013

A Tight Bound for Set Disjointness in the Message-Passing Model.

Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Value Elimination: Bayesian Inference via Backtracking Search

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi

CoRR, 2012

A little advice can be very helpful.

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Fairness through awareness.

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Communication Complexity and Information Complexity: Foundations and New Directions.

Toniann Pitassi

Proceedings of the 27th Conference on Computational Complexity, 2012

Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems.

Per Austrin, Toniann Pitassi, Yu Wu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

The Limits of Two-Party Differential Privacy.

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2011

Special Issue In Memory of Misha Alekhnovich. Foreword.

Allan Borodin, Toniann Pitassi, Alexander A. Razborov

Comput. Complex., 2011

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi

Comput. Complex., 2011

Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results.

Toniann Pitassi

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

Automatizability and Simple Stochastic Games.

Lei Huang, Toniann Pitassi

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Separating Deterministic from Randomized Multiparty Communication Complexity.

Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel

Theory Comput., 2010

The story of set disjointness.

Arkadev Chattopadhyay, Toniann Pitassi

SIGACT News, 2010

The PSPACE-Completeness of Black-White Pebbling.

Philipp Hertel, Toniann Pitassi

SIAM J. Comput., 2010

Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy.

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis

SIAM J. Comput., 2010

Differential privacy under continual observation.

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Hardness amplification in proof complexity.

Paul Beame, Trinh Huynh, Toniann Pitassi

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Effectively Polynomial Simulations.

Toniann Pitassi, Rahul Santhanam

Proceedings of the Innovations in Computer Science, 2010

Pan-Private Streaming Algorithms.

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, Sergey Yekhanin

Proceedings of the Innovations in Computer Science, 2010

2009

Improved Separations between Nondeterministic and Randomized Multiparty Communication.

Matei David, Toniann Pitassi, Emanuele Viola

ACM Trans. Comput. Theory, 2009

Solving #SAT and Bayesian Inference with Backtracking Search.

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi

J. Artif. Intell. Res., 2009

2008

Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table.

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks

SIAM J. Comput., 2008

The complexity of properly learning simple concept classes.

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi

J. Comput. Syst. Sci., 2008

Separating NOF communication complexity classes RP and NP.

Matei David, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2008

Clause Learning Can Effectively P-Simulate General Propositional Resolution.

Philipp Hertel, Fahiem Bacchus, Toniann Pitassi, Allen Van Gelder

Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007

An Exponential Separation between Regular and General Resolution.

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart

Theory Comput., 2007

Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.

Paul Beame, Toniann Pitassi, Nathan Segerlind

SIAM J. Comput., 2007

The complexity of resolution refinements.

Joshua Buresh-Oppenheim, Toniann Pitassi

J. Symb. Log., 2007

Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.

Nathan Segerlind, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2007

An Exponential Time/Space Speedup For Resolution.

Philipp Hertel, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2007

Black-White Pebbling is PSPACE-Complete.

Philipp Hertel, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2007

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.

Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.

Philipp Hertel, Toniann Pitassi

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Rank Bounds and Integrality Gaps for Cutting Planes Procedures.

Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi

Theory Comput., 2006

The complexity of analytic tableaux.

Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart

J. Symb. Log., 2006

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.

Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis

Electron. Colloquium Comput. Complex., 2006

Formula Caching in DPLL.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2006

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Comput. Complex., 2006

Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives.

Alexis Maciel, Toniann Pitassi

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Minimizing DNF Formulas and AC⁰_d Circuits Given a Truth Table.

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Monotone Circuits for the Majority Function.

Shlomo Hoory, Avner Magen, Toniann Pitassi

Proceedings of the Approximation, 2006

2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks

Electron. Colloquium Comput. Complex., 2005

Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

Paul Beame, Toniann Pitassi, Nathan Segerlind

Electron. Colloquium Comput. Complex., 2005

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.

Toniann Pitassi, Ran Raz

Comb., 2004

Non-Automatizability of Bounded-Depth Frege Proofs.

Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi

Comput. Complex., 2004

Combining Component Caching and Clause Learning for Effective Model Counting.

Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi

Proceedings of the SAT 2004, 2004

Learnability and Automatizability.

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

DPLL with Caching: A new algorithm for #SAT and Bayesian Inference

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2003

Value Elimination: Bayesian Interence via Backtracking Search.

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi

Proceedings of the UAI '03, 2003

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.

Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Algorithms and Complexity Results for #SAT and Bayesian Inference.

Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Memoization and DPLL: Formula Caching Proof Systems.

Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

The Efficiency of Resolution and Davis--Putnam Procedures.

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks

SIAM J. Comput., 2002

A New Proof of the Weak Pigeonhole Principle.

Alexis Maciel, Toniann Pitassi, Alan R. Woods

J. Comput. Syst. Sci., 2002

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal

Electron. Colloquium Comput. Complex., 2002

Homogenization and the polynomial calculus.

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi

Comput. Complex., 2002

2001

Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.

Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi

J. Symb. Log., 2001

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi

J. Comput. Syst. Sci., 2001

Stochastic Boolean Satisfiability.

Michael L. Littman, Stephen M. Majercik, Toniann Pitassi

J. Autom. Reason., 2001

Linear and Negative Resolution are Weaker than Resolution

Josh Buresh-Oppenheim, David G. Mitchell, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2001

Reducing the complexity of reductions.

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

Comput. Complex., 2001

Propositional Proof Complexity: Past, Present, and Future.

Paul Beame, Toniann Pitassi

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

On Interpolation and Automatization for Frege Systems.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

SIAM J. Comput., 2000

A Gradient-Based Boosting Algorithm for Regression Problems.

Richard S. Zemel, Toniann Pitassi

Proceedings of the Advances in Neural Information Processing Systems 13, 2000

Homogenization and the Polynominal Calculus.

Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.

Samuel R. Buss, Toniann Pitassi

J. Comput. Syst. Sci., 1998

The Relative Complexity of NP Search Problems.

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi

J. Comput. Syst. Sci., 1998

Propositional Proof Complexity: Past, Present and Future

Paul Beame, Toniann Pitassi

Electron. Colloquium Comput. Complex., 1998

Improved Depth Lower Bounds for Small Distance Connectivity.

Paul Beame, Russell Impagliazzo, Toniann Pitassi

Comput. Complex., 1998

On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

Lower Bounds for Cutting Planes Proofs with Small Coefficients.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

J. Symb. Log., 1997

On ACC⁰[<i>p^k</i>] Frege Proofs.

Alexis Maciel, Toniann Pitassi

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

No Feasible Interpolation for TC0-Frege Proofs.

Maria Luisa Bonet, Toniann Pitassi, Ran Raz

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Resolution and the Weak Pigeonhole Principle.

Samuel R. Buss, Toniann Pitassi

Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996

The future of computational complexity theory: part II.

Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich

SIGACT News, 1996

An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.

Paul Beame, Toniann Pitassi

Ann. Pure Appl. Log., 1996

Simplified and Improved Resolution Lower Bounds.

Paul Beame, Toniann Pitassi

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Algebraic Propositional Proof Systems.

Toniann Pitassi

Proceedings of the Descriptive Complexity and Finite Models, 1996

Towards lower bounds for bounded-depth Frege proofs with modular connectives.

Alexis Maciel, Toniann Pitassi

Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995

The Complexity of the Hajos Calculus.

Toniann Pitassi, Alasdair Urquhart

SIAM J. Discret. Math., 1995

Exponential Lower Bounds for the Tree-Like Hajós Calculus.

Kazuo Iwama, Toniann Pitassi

Inf. Process. Lett., 1995

Improved Depth Lower Vounds for Small Distance Connectivity.

Paul Beame, Russell Impagliazzo, Toniann Pitassi

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Upper and Lower Bounds for Tree-Like Cutting Planes Proofs

Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart

Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Semantics of Nondeterministic Asynchronous Broadcast Networks

R. K. Shyamasundar, K. T. Narayana, Toniann Pitassi

Inf. Comput., June, 1993

Exponential Lower Bounds for the Pigeonhole Principle.

Toniann Pitassi, Paul Beame, Russell Impagliazzo

Comput. Complex., 1993

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

Paul Beame, Toniann Pitassi

Proceedings of the Eighth Annual Symposium on Logic in Computer Science (LICS '93), 1993

1992

The power of weak formal systems.

Toniann Pitassi

PhD thesis, 1992

Approximation and Small-Depth Frege Proofs.

Stephen J. Bellantoni, Toniann Pitassi, Alasdair Urquhart

SIAM J. Comput., 1992

Exponential Lower Bounds for the Pigeonhole Principle

Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1990

A Feasibly Constructive Lower Bound for Resolution Proofs.

Stephen A. Cook, Toniann Pitassi

Inf. Process. Lett., 1990