A Feasibly Constructive Lower Bound for Resolution Proofs. - Stephen A. Cook; Toniann Pitassi (Inf. Process. Lett., 1990)

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

Approximation and Small-Depth Frege Proofs. - Stephen J. Bellantoni; Toniann Pitassi; Alasdair Urquhart (SIAM J. Comput., 1992)

The power of weak formal systems. - Toniann Pitassi (1992)

An Exponential Separation between the Matching Principle and the Pigeonhole Principle - Paul Beame; Toniann Pitassi (LICS, 1993)

Exponential Lower Bounds for the Pigeonhole Principle. - Toniann Pitassi; Paul Beame; Russell Impagliazzo (Comput. Complex., 1993)

Semantics of Nondeterministic Asynchronous Broadcast Networks - R. K. Shyamasundar; K. T. Narayana; Toniann Pitassi (Inf. Comput., 1993)

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

Upper and Lower Bounds for Tree-Like Cutting Planes Proofs - Russell Impagliazzo; Toniann Pitassi; Alasdair Urquhart (LICS, 1994)

Improved Depth Lower Vounds for Small Distance Connectivity. - Paul Beame; Russell Impagliazzo; Toniann Pitassi (FOCS, 1995)

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

The Complexity of the Hajos Calculus. - Toniann Pitassi; Alasdair Urquhart (SIAM J. Discret. Math., 1995)

Towards lower bounds for bounded-depth Frege proofs with modular connectives. - Alexis Maciel; Toniann Pitassi (Proof Complexity and Feasible Arithmetics, 1996)

Algebraic Propositional Proof Systems. - Toniann Pitassi (Descriptive Complexity and Finite Models, 1996)

Simplified and Improved Resolution Lower Bounds. - Paul Beame; Toniann Pitassi (FOCS, 1996)

An Exponential Separation Between the Parity Principle and the Pigeonhole Principle. - Paul Beame; Toniann Pitassi (Ann. Pure Appl. Log., 1996)

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

Resolution and the Weak Pigeonhole Principle. - Samuel R. Buss; Toniann Pitassi (CSL, 1997)

No Feasible Interpolation for TC0-Frege Proofs. - Maria Luisa Bonet; Toniann Pitassi; Ran Raz (FOCS, 1997)

On ACC0[pk] Frege Proofs. - Alexis Maciel; Toniann Pitassi (STOC, 1997)

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

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

Improved Depth Lower Bounds for Small Distance Connectivity. - Paul Beame; Russell Impagliazzo; Toniann Pitassi (Comput. Complex., 1998)

Propositional Proof Complexity: Past, Present and Future - Paul Beame; Toniann Pitassi (Electron. Colloquium Comput. Complex., 1998)

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

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

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). - Samuel R. Buss; Dima Grigoriev; Russell Impagliazzo; Toniann Pitassi (CCC, 1999)

Homogenization and the Polynominal Calculus. - Josh Buresh-Oppenheim; Matthew Clegg; Russell Impagliazzo; Toniann Pitassi (ICALP, 2000)

A Gradient-Based Boosting Algorithm for Regression Problems. - Richard S. Zemel; Toniann Pitassi (NIPS, 2000)

On Interpolation and Automatization for Frege Systems. - Maria Luisa Bonet; Toniann Pitassi; Ran Raz (SIAM J. Comput., 2000)

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

Reducing the complexity of reductions. - Manindra Agrawal; Eric Allender; Russell Impagliazzo; Toniann Pitassi; Steven Rudich (Comput. Complex., 2001)

An Exponential Separation between Regular and General Resolution - Michael Alekhnovich; Jan Johannsen; Toniann Pitassi; Alasdair Urquhart (Electron. Colloquium Comput. Complex., 2001)

Linear and Negative Resolution are Weaker than Resolution - Josh Buresh-Oppenheim; David G. Mitchell; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2001)

Stochastic Boolean Satisfiability. - Michael L. Littman; Stephen M. Majercik; Toniann Pitassi (J. Autom. Reason., 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)

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

Homogenization and the polynomial calculus. - Josh Buresh-Oppenheim; Matthew Clegg; Russell Impagliazzo; Toniann Pitassi (Comput. Complex., 2002)

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

The Efficiency of Resolution and Davis–Putnam Procedures. - Paul Beame; Richard M. Karp; Toniann Pitassi; Michael E. Saks (SIAM J. Comput., 2002)

Memoization and DPLL: Formula Caching Proof Systems. - Paul Beame; Russell Impagliazzo; Toniann Pitassi; Nathan Segerlind (CCC, 2003)

Algorithms and Complexity Results for #SAT and Bayesian Inference. - Fahiem Bacchus; Shannon Dalmao; Toniann Pitassi (FOCS, 2003)

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

Value Elimination: Bayesian Interence via Backtracking Search. - Fahiem Bacchus; Shannon Dalmao; Toniann Pitassi (UAI, 2003)

DPLL with Caching: A new algorithm for #SAT and Bayesian Inference - Fahiem Bacchus; Shannon Dalmao; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2003)

Learnability and Automatizability. - Michael Alekhnovich; Mark Braverman; Vitaly Feldman; Adam R. Klivans; Toniann Pitassi (FOCS, 2004)

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

Non-Automatizability of Bounded-Depth Frege Proofs. - Maria Luisa Bonet; Carlos Domingo; Ricard Gavaldà; Alexis Maciel; Toniann Pitassi (Comput. Complex., 2004)

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle. - Toniann Pitassi; Ran Raz (Comb., 2004)

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

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. - Paul Beame; Toniann Pitassi; Nathan Segerlind; Avi Wigderson (CCC, 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)

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)

Monotone Circuits for the Majority Function. - Shlomo Hoory; Avner Magen; Toniann Pitassi (APPROX-RANDOM, 2006)

Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. - Eric Allender; Lisa Hellerstein; Paul McCabe; Toniann Pitassi; Michael E. Saks (CCC, 2006)

Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives. - Alexis Maciel; Toniann Pitassi (LICS, 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)

Formula Caching in DPLL. - Paul Beame; Russell Impagliazzo; Toniann Pitassi; Nathan Segerlind (Electron. Colloquium Comput. Complex., 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)

The complexity of analytic tableaux. - Noriko H. Arai; Toniann Pitassi; Alasdair Urquhart (J. Symb. Log., 2006)

Rank Bounds and Integrality Gaps for Cutting Planes Procedures. - Joshua Buresh-Oppenheim; Nicola Galesi; Shlomo Hoory; Avner Magen; Toniann Pitassi (Theory Comput., 2006)

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

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

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. - Paul Beame; Matei David; Toniann Pitassi; Philipp Woelfel (ICALP, 2007)

Black-White Pebbling is PSPACE-Complete. - Philipp Hertel; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2007)

An Exponential Time/Space Speedup For Resolution. - Philipp Hertel; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2007)

The complexity of resolution refinements. - Joshua Buresh-Oppenheim; Toniann Pitassi (J. Symb. Log., 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)

Clause Learning Can Effectively P-Simulate General Propositional Resolution. - Philipp Hertel; Fahiem Bacchus; Toniann Pitassi; Allen Van Gelder (AAAI, 2008)

Separating NOF communication complexity classes RP and NP. - Matei David; Toniann Pitassi (Electron. Colloquium Comput. Complex., 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)

Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. - Eric Allender; Lisa Hellerstein; Paul McCabe; Toniann Pitassi; Michael E. Saks (SIAM J. Comput., 2008)

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

Improved Separations between Nondeterministic and Randomized Multiparty Communication. - Matei David; Toniann Pitassi; Emanuele Viola (ACM Trans. Comput. Theory, 2009)

Pan-Private Streaming Algorithms. - Cynthia Dwork; Moni Naor; Toniann Pitassi; Guy N. Rothblum; Sergey Yekhanin (ICS, 2010)

Effectively Polynomial Simulations. - Toniann Pitassi; Rahul Santhanam (ICS, 2010)

Hardness amplification in proof complexity. - Paul Beame; Trinh Huynh; Toniann Pitassi (STOC, 2010)

Differential privacy under continual observation. - Cynthia Dwork; Moni Naor; Toniann Pitassi; Guy N. Rothblum (STOC, 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)

The PSPACE-Completeness of Black-White Pebbling. - Philipp Hertel; Toniann Pitassi (SIAM J. Comput., 2010)

The story of set disjointness. - Arkadev Chattopadhyay; Toniann Pitassi (SIGACT News, 2010)

Separating Deterministic from Randomized Multiparty Communication Complexity. - Paul Beame; Matei David; Toniann Pitassi; Philipp Woelfel (Theory Comput., 2010)

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

Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results. - Toniann Pitassi (LICS, 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)

Special Issue In Memory of Misha Alekhnovich. Foreword. - Allan Borodin; Toniann Pitassi; Alexander A. Razborov (Comput. Complex., 2011)

The Limits of Two-Party Differential Privacy. - Andrew McGregor 001; Ilya Mironov; Toniann Pitassi; Omer Reingold; Kunal Talwar; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2011)

Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. - Per Austrin; Toniann Pitassi; Yu Wu (APPROX-RANDOM, 2012)

Communication Complexity and Information Complexity: Foundations and New Directions. - Toniann Pitassi (CCC, 2012)

Fairness through awareness. - Cynthia Dwork; Moritz Hardt; Toniann Pitassi; Omer Reingold; Richard S. Zemel (ITCS, 2012)

A little advice can be very helpful. - Arkadev Chattopadhyay; Jeff Edmonds; Faith Ellen; Toniann Pitassi (SODA, 2012)

Value Elimination: Bayesian Inference via Backtracking Search - Fahiem Bacchus; Shannon Dalmao; Toniann Pitassi (CoRR, 2012)

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

A Tight Bound for Set Disjointness in the Message-Passing Model. - Mark Braverman; Faith Ellen; Rotem Oshman; Toniann Pitassi; Vinod Vaikuntanathan (FOCS, 2013)

Learning Fair Representations. - Richard S. Zemel; Yu Wu; Kevin Swersky; Toniann Pitassi; Cynthia Dwork (ICML (3), 2013)

On the Expressive Power of Restricted Boltzmann Machines. - James Martens; Arkadev Chattopadhyay; Toniann Pitassi; Richard S. Zemel (NIPS, 2013)

Tight Bounds for Set Disjointness in the Message Passing Model - Mark Braverman; Faith Ellen; Rotem Oshman; Toniann Pitassi; Vinod Vaikuntanathan (CoRR, 2013)

Average Case Lower Bounds for Monotone Switching Networks. - Yuval Filmus; Toniann Pitassi; Robert Robere; Stephen A. Cook (Electron. Colloquium Comput. Complex., 2013)

Lifting lower bounds for tree-like proofs. - Alexis Maciel; Phuong Nguyen 001; Toniann Pitassi (Comput. Complex., 2014)

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. - Mika Göös; Toniann Pitassi; Thomas Watson 001 (Electron. Colloquium Comput. Complex., 2014)

Circuit complexity, proof complexity, and polynomial identity testing. - Joshua A. Grochow; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2014)

Inapproximability of Treewidth and Related Problems. - Yu (Ledell) Wu; Per Austrin; Toniann Pitassi; David Liu 003 (J. Artif. Intell. Res., 2014)

The Hardness of Being Private. - Anil Ada; Arkadev Chattopadhyay; Stephen A. Cook; Lila Fontes; Michal Koucký 001; Toniann Pitassi (ACM Trans. Comput. Theory, 2014)

Inapproximability of Treewidth and Related Problems (Extended Abstract). - Yu (Ledell) Wu; Per Austrin; Toniann Pitassi; David Liu 003 (IJCAI, 2015)

Generalization in Adaptive Data Analysis and Holdout Reuse. - Cynthia Dwork; Vitaly Feldman; Moritz Hardt; Toniann Pitassi; Omer Reingold; Aaron Roth 001 (NIPS, 2015)

Preserving Statistical Validity in Adaptive Data Analysis. - Cynthia Dwork; Vitaly Feldman; Moritz Hardt; Toniann Pitassi; Omer Reingold; Aaron Leon Roth (STOC, 2015)

Randomized Communication vs. Partition Number. - Mika Göös; T. S. Jayram; Toniann Pitassi; Thomas Watson 001 (Electron. Colloquium Comput. Complex., 2015)

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. - Yuval Filmus; Toniann Pitassi; Rahul Santhanam (ACM Trans. Comput. Theory, 2015)

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. - Stephen A. Cook; Jeff Edmonds; Venkatesh Medabalimi; Toniann Pitassi (ICALP, 2016)

Poly-logarithmic Frege depth lower bounds via an expander switching lemma. - Toniann Pitassi; Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (STOC, 2016)

Exponential Lower Bounds for Monotone Span Programs. - Stephen A. Cook; Toniann Pitassi; Robert Robere; Benjamin Rossman (Electron. Colloquium Comput. Complex., 2016)

Strongly Exponential Lower Bounds for Monotone Computation. - Toniann Pitassi; Robert Robere (Electron. Colloquium Comput. Complex., 2016)

Algebraic Proof Complexity: Progress, Frontiers and Challenges. - Toniann Pitassi; Iddo Tzameret (Electron. Colloquium Comput. Complex., 2016)

Upper and Lower Bounds on the Power of Advice. - Arkadev Chattopadhyay; Jeff Edmonds; Faith Ellen; Toniann Pitassi (SIAM J. Comput., 2016)

Random Θ(log n)-CNFs Are Hard for Cutting Planes. - Noah Fleming; Denis Pankratov; Toniann Pitassi; Robert Robere (FOCS, 2017)

Guilt-free data reuse. - Cynthia Dwork; Vitaly Feldman; Moritz Hardt; Toniann Pitassi; Omer Reingold; Aaron Roth 001 (Commun. ACM, 2017)

Stabbing Planes. - Paul Beame; Noah Fleming; Russell Impagliazzo; Antonina Kolokolova; Denis Pankratov; Toniann Pitassi; Robert Robere (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)

Lifting Nullstellensatz to Monotone Span Programs over Any Field. - Toniann Pitassi; Robert Robere (Electron. Colloquium Comput. Complex., 2017)

Hardness of Function Composition for Semantic Read once Branching Programs. - Jeff Edmonds; Venkatesh Medabalimi; Toniann Pitassi (CCC, 2018)

Predict Responsibly: Increasing Fairness by Learning to Defer. - David Madras; Toniann Pitassi; Richard S. Zemel (ICLR (Workshop), 2018)

Learning Adversarially Fair and Transferable Representations. - David Madras; Elliot Creager; Toniann Pitassi; Richard S. Zemel (ICML, 2018)

Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer. - David Madras; Toniann Pitassi; Richard S. Zemel (NeurIPS, 2018)

The Landscape of Communication Complexity Classes. - Mika Göös; Toniann Pitassi; Thomas Watson 001 (Comput. Complex., 2018)

Fairness Through Causal Awareness: Learning Latent-Variable Models for Biased Data. - David Madras; Elliot Creager; Toniann Pitassi; Richard S. Zemel (CoRR, 2018)

Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System. - Joshua A. Grochow; Toniann Pitassi (J. ACM, 2018)

Deterministic Communication vs. Partition Number. - Mika Göös; Toniann Pitassi; Thomas Watson 001 (SIAM J. Comput., 2018)

Communication Lower Bounds via Critical Block Sensitivity. - Mika Göös; Toniann Pitassi (SIAM J. Comput., 2018)

Randomized Communication versus Partition Number. - Mika Göös; T. S. Jayram; Toniann Pitassi; Thomas Watson 001 (ACM Trans. Comput. Theory, 2018)

Fairness through Causal Awareness: Learning Causal Latent-Variable Models for Biased Data. - David Madras; Elliot Creager; Toniann Pitassi; Richard S. Zemel (FAT, 2019)

Progress in Lifting and Applications in Lower Bounds (Invited Talk). - Toniann Pitassi (FSTTCS, 2019)

Query-To-Communication Lifting for BPP Using Inner Product. - Arkadev Chattopadhyay; Yuval Filmus; Sajin Koroth; Or Meir; Toniann Pitassi (ICALP, 2019)

Short Proofs Are Hard to Find. - Ian Mertz; Toniann Pitassi; Yuanhao Wei (ICALP, 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 (ICML, 2019)

On the Communication Complexity of High-Dimensional Permutations. - Nati Linial; Toniann Pitassi; Adi Shraibman (ITCS, 2019)

Query-to-Communication Lifting for P NP. - Mika Göös; Pritish Kamath; Toniann Pitassi; Thomas Watson 001 (Comput. Complex., 2019)

Correction to: Query-to-Communication Lifting for P NP. - Mika Göös; Pritish Kamath; Toniann Pitassi; Thomas Watson 001 (Comput. Complex., 2019)

Semialgebraic Proofs and Efficient Algorithm Design. - Noah Fleming; Pravesh Kothari; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2019)

The Surprising Power of Constant Depth Algebraic Proofs. - Russell Impagliazzo; Sasank Mouli; Toniann Pitassi (Electron. Colloquium Comput. Complex., 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)

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 (FOCS, 2020)

Causal Modeling for Fairness In Dynamical Systems. - Elliot Creager; David Madras; Toniann Pitassi; Richard S. Zemel (ICML, 2020)

Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers. - Chunxiao Li 002; Noah Fleming; Marc Vinyals; Toniann Pitassi; Vijay Ganesh 001 (SAT, 2020)

Automating Cutting Planes is NP-Hard. - Mika Göös; Sajin Koroth; 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 001; Susanna F. de Rezende (Electron. Colloquium Comput. Complex., 2020)

Lifting: As Easy As 1, 2, 3. - Ian Mertz; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2020)

Query-to-Communication Lifting for BPP. - Mika Göös; Toniann Pitassi; Thomas Watson 001 (SIAM J. Comput., 2020)

On the Pseudo-Deterministic Query Complexity of NP Search Problems. - Shafi Goldwasser; Russell Impagliazzo; Toniann Pitassi; Rahul Santhanam (CCC, 2021)

Size and Depth Separation in Approximating Benign Functions with Neural Networks. - Gal Vardi; Daniel Reichman 001; Toniann Pitassi; Ohad Shamir (COLT, 2021)

Tradeoffs for small-depth Frege proofs. - Toniann Pitassi; Prasanna Ramakrishnan; Li-Yang Tan (FOCS, 2021)

Algebraic Proof Systems (Invited Talk). - Toniann Pitassi (ICALP, 2021)

Theoretical bounds on estimation error for meta-learning. - James Lucas; Mengye Ren; Irene Raissa Kameni; Toniann Pitassi; Richard S. Zemel (ICLR, 2021)

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. - Toniann Pitassi; Morgan Shirley; Thomas Watson 001 (Comput. Complex., 2021)

Size and Depth Separation in Approximating Natural Functions with Neural Networks. - Gal Vardi; Daniel Reichman 001; Toniann Pitassi; Ohad Shamir (CoRR, 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)

Reflections on Proof Complexity and Counting Principles. - Noah Fleming; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2021)

Extremely Deep Proofs. - Noah Fleming; Toniann Pitassi; Robert Robere (Electron. Colloquium Comput. Complex., 2021)

Query-to-Communication Lifting Using Low-Discrepancy Gadgets. - Arkadev Chattopadhyay; Yuval Filmus; Sajin Koroth; Or Meir; Toniann Pitassi (SIAM J. Comput., 2021)

Lifting with Sunflowers. - Shachar Lovett; Raghu Meka; Ian Mertz; Toniann Pitassi; Jiapeng Zhang (ITCS, 2022)

On Learning and Refutation in Noninteractive Local Differential Privacy. - Alexander Edmonds; Aleksandar Nikolov; Toniann Pitassi (NeurIPS, 2022)

Reproducibility in learning. - Russell Impagliazzo; Rex Lei; Toniann Pitassi; Jessica Sorrell (STOC, 2022)

Learning versus Refutation in Noninteractive Local Differential Privacy. - Alexander Edmonds; Aleksandar Nikolov; Toniann Pitassi (CoRR, 2022)

Secret Sharing, Slice Formulas, and Monotone Real Circuits. - Benny Applebaum; Amos Beimel; Oded Nir; Naty Peter; Toniann Pitassi (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)

The Strength of Equality Oracles in Communication. - Toniann Pitassi; Morgan Shirley; Adi Shraibman (Electron. Colloquium Comput. Complex., 2022)

Random ( Theta ( log n) ) -CNFs are Hard for Cutting Planes. - Noah Fleming; Denis Pankratov; Toniann Pitassi; Robert Robere (J. ACM, 2022)

On the Algebraic Proof Complexity of Tensor Isomorphism. - Nicola Galesi; Joshua A. Grochow; Toniann Pitassi; Adrian She (CCC, 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 (ICLR, 2023)

Distribution-Free Statistical Dispersion Control for Societal Applications. - Zhun Deng; Thomas P. Zollo; Jake Snell; Toniann Pitassi; Richard S. Zemel (NeurIPS, 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 (STOC, 2023)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. - Kasper Green Larsen; Rasmus Pagh; Toniann Pitassi; Or Zamir (CoRR, 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)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. - Kasper Green Larsen; Rasmus Pagh; Giuseppe Persiano; Toniann Pitassi; Kevin Yeo; Or Zamir (ICALP, 2024)

Prompt Risk Control: A Rigorous Framework for Responsible Deployment of Large Language Models. - Thomas P. Zollo; Todd Morrill; Zhun Deng; Jake Snell; Toniann Pitassi; Richard S. Zemel (ICLR, 2024)

A Lower Bound on the Trace Norm of Boolean Matrices and its Applications. - Tsun-Ming Cheung; Hamed Hatami; Kaave Hosseini; Aleksandar Nikolov; Toniann Pitassi; Morgan Shirley (Electron. Colloquium Comput. Complex., 2024)

Black-Box PPP is not Turing-Closed. - Noah Fleming; Stefan Grosser; Toniann Pitassi; Robert Robere (Electron. Colloquium Comput. Complex., 2024)

Strong vs. Weak Range Avoidance and the Linear Ordering Principle. - Oliver Korten; Toniann Pitassi (Electron. Colloquium Comput. Complex., 2024)

Improving Predictor Reliability with Selective Recalibration. - Thomas P. Zollo; Zhun Deng; Jake Snell; Toniann Pitassi; Richard S. Zemel (Trans. Mach. Learn. Res., 2024)

KRW Composition Theorems via Lifting. - Susanna F. de Rezende; Or Meir; Jakob Nordström; Toniann Pitassi; Robert Robere (Comput. Complex., 2024)

Testing Juntas and Junta Subclasses with Relative Error. - Xi Chen 001; William Pires; Toniann Pitassi; Rocco A. Servedio (COLT, 2025)

Relative-Error Testing of Conjunctions and Decision Lists. - Xi Chen 001; William Pires; Toniann Pitassi; Rocco A. Servedio (ICALP, 2025)

Stronger Cell Probe Lower Bounds via Local PRGs. - Oliver Korten; Toniann Pitassi; Russell Impagliazzo (Electron. Colloquium Comput. Complex., 2025)

Fully-Fluctuating Participation in Sleepy Consensus. - Yuval Efron; Joachim Neu; Toniann Pitassi (IACR Cryptol. ePrint Arch., 2025)

Replay Can Provably Increase Forgetting. - Yasaman Mahdaviyeh; James Lucas; Mengye Ren; Andreas S. Tolias; Richard S. Zemel; Toniann Pitassi (CoRR, 2025)