Toniann Pitassi

According to our database1, Toniann Pitassi authored at least 148 papers between 1990 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2018, "For contributions to research and education in the fields of computational and proof complexity".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
KRW Composition Theorems via Lifting.
Electronic Colloquium on Computational Complexity (ECCC), 2020

Automating Algebraic Proof Systems is NP-Hard.
Electronic Colloquium on Computational Complexity (ECCC), 2020

Automating Cutting Planes is NP-Hard.
Electronic Colloquium on Computational Complexity (ECCC), 2020

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.
CoRR, 2020

Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

2019
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2019

The Surprising Power of Constant Depth Algebraic Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Semialgebraic Proofs and Efficient Algorithm Design.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Query-to-Communication Lifting Using Low-Discrepancy Gadgets.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Causal Modeling for Fairness in Dynamical Systems.
CoRR, 2019

Correction to: Query-to-Communication Lifting for P NP.
Comput. Complex., 2019

Query-to-Communication Lifting for P NP.
Comput. Complex., 2019

On the Communication Complexity of High-Dimensional Permutations.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Flexibly Fair Representation Learning by Disentanglement.
Proceedings of the 36th International Conference on Machine Learning, 2019

Short Proofs Are Hard to Find.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Query-To-Communication Lifting for BPP Using Inner Product.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Progress in Lifting and Applications in Lower Bounds (Invited Talk).
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.
Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

2018
Randomized Communication versus Partition Number.
ACM Trans. Comput. Theory, 2018

Communication Lower Bounds via Critical Block Sensitivity.
SIAM J. Comput., 2018

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

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

The Landscape of Communication Complexity Classes.
Comput. Complex., 2018

Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer.
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.
Proceedings of the 35th International Conference on Machine Learning, 2018

Predict Responsibly: Increasing Fairness by Learning to Defer.
Proceedings of the 6th International Conference on Learning Representations, 2018

Hardness of Function Composition for Semantic Read once Branching Programs.
Proceedings of the 33rd Computational Complexity Conference, 2018

2017
Lifting Nullstellensatz to Monotone Span Programs over Any Field.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Query-to-Communication Lifting for BPP.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Random CNFs are Hard for Cutting Planes.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Stabbing Planes.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Guilt-free data reuse.
Commun. ACM, 2017

Random Θ(log n)-CNFs Are Hard for Cutting Planes.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Algebraic proof complexity: progress, frontiers and challenges.
ACM SIGLOG News, 2016

Upper and Lower Bounds on the Power of Advice.
SIAM J. Comput., 2016

Strongly Exponential Lower Bounds for Monotone Computation.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Exponential Lower Bounds for Monotone Span Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.
Algorithmica, 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Exponential Lower Bounds for AC<sup>0</sup>-Frege Imply Superpolynomial Frege Lower Bounds.
ACM Trans. Comput. Theory, 2015

Deterministic Communication vs. Partition Number.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Randomized Communication vs. Partition Number.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Preserving Statistical Validity in Adaptive Data Analysis.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Generalization in Adaptive Data Analysis and Holdout Reuse.
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).
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014
The Hardness of Being Private.
ACM Trans. Comput. Theory, 2014

Inapproximability of Treewidth and Related Problems.
J. Artif. Intell. Res., 2014

Circuit complexity, proof complexity, and polynomial identity testing.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Lifting lower bounds for tree-like proofs.
Comput. Complex., 2014

2013
Average Case Lower Bounds for Monotone Switching Networks.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Tight Bounds for Set Disjointness in the Message Passing Model
CoRR, 2013

On the Expressive Power of Restricted Boltzmann Machines.
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.
Proceedings of the 30th International Conference on Machine Learning, 2013

A Tight Bound for Set Disjointness in the Message-Passing Model.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Value Elimination: Bayesian Inference via Backtracking Search
CoRR, 2012

A little advice can be very helpful.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Fairness through awareness.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Communication Complexity and Information Complexity: Foundations and New Directions.
Proceedings of the 27th Conference on Computational Complexity, 2012

Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
The Limits of Two-Party Differential Privacy.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Special Issue In Memory of Misha Alekhnovich. Foreword.
Comput. Complex., 2011

Toward a Model for Backtracking and Dynamic Programming.
Comput. Complex., 2011

Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results.
Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

Automatizability and Simple Stochastic Games.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Separating Deterministic from Randomized Multiparty Communication Complexity.
Theory Comput., 2010

The story of set disjointness.
SIGACT News, 2010

The PSPACE-Completeness of Black-White Pebbling.
SIAM J. Comput., 2010

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

Differential privacy under continual observation.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Hardness amplification in proof complexity.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Effectively Polynomial Simulations.
Proceedings of the Innovations in Computer Science, 2010

Pan-Private Streaming Algorithms.
Proceedings of the Innovations in Computer Science, 2010

2009
Improved Separations between Nondeterministic and Randomized Multiparty Communication.
ACM Trans. Comput. Theory, 2009

Solving #SAT and Bayesian Inference with Backtracking Search.
J. Artif. Intell. Res., 2009

2008
Minimizing Disjunctive Normal Form Formulas and AC<sup>0</sup> Circuits Given a Truth Table.
SIAM J. Comput., 2008

The complexity of properly learning simple concept classes.
J. Comput. Syst. Sci., 2008

Separating NOF communication complexity classes RP and NP.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Clause Learning Can Effectively P-Simulate General Propositional Resolution.
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007
An Exponential Separation between Regular and General Resolution.
Theory Comput., 2007

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

The complexity of resolution refinements.
J. Symb. Log., 2007

Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.
Electronic Colloquium on Computational Complexity (ECCC), 2007

An Exponential Time/Space Speedup For Resolution.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Black-White Pebbling is PSPACE-Complete.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.
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.
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.
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.
Theory Comput., 2006

The complexity of analytic tableaux.
J. Symb. Log., 2006

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Formula Caching in DPLL.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Comput. Complex., 2006

Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives.
Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Minimizing DNF Formulas and AC<sup>0</sup><sub>d</sub> Circuits Given a Truth Table.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Monotone Circuits for the Majority Function.
Proceedings of the Approximation, 2006

2005
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electronic Colloquium on Computational Complexity (ECCC), 2005

Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Electronic Colloquium on Computational Complexity (ECCC), 2005

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.
Comb., 2004

Non-Automatizability of Bounded-Depth Frege Proofs.
Comput. Complex., 2004

Combining Component Caching and Clause Learning for Effective Model Counting.
Proceedings of the SAT 2004, 2004

Learnability and Automatizability.
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
Electronic Colloquium on Computational Complexity (ECCC), 2003

Value Elimination: Bayesian Interence via Backtracking Search.
Proceedings of the UAI '03, 2003

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Algorithms and Complexity Results for #SAT and Bayesian Inference.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Memoization and DPLL: Formula Caching Proof Systems.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
The Efficiency of Resolution and Davis--Putnam Procedures.
SIAM J. Comput., 2002

A New Proof of the Weak Pigeonhole Principle.
J. Comput. Syst. Sci., 2002

Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium on Computational Complexity (ECCC), 2002

Homogenization and the polynomial calculus.
Comput. Complex., 2002

2001
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.
J. Symb. Log., 2001

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.
J. Comput. Syst. Sci., 2001

Stochastic Boolean Satisfiability.
J. Autom. Reasoning, 2001

Linear and Negative Resolution are Weaker than Resolution
Electronic Colloquium on Computational Complexity (ECCC), 2001

Reducing the complexity of reductions.
Comput. Complex., 2001

Propositional Proof Complexity: Past, Present, and Future.
Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000
On Interpolation and Automatization for Frege Systems.
SIAM J. Comput., 2000

A Gradient-Based Boosting Algorithm for Regression Problems.
Proceedings of the Advances in Neural Information Processing Systems 13, 2000

Homogenization and the Polynominal Calculus.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
J. Comput. Syst. Sci., 1998

The Relative Complexity of NP Search Problems.
J. Comput. Syst. Sci., 1998

Propositional Proof Complexity: Past, Present and Future
Electronic Colloquium on Computational Complexity (ECCC), 1998

Improved Depth Lower Bounds for Small Distance Connectivity.
Comput. Complex., 1998

On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997
Lower Bounds for Cutting Planes Proofs with Small Coefficients.
J. Symb. Log., 1997

On ACC<sup>0</sup>[<i>p<sup>k</sup></i>] Frege Proofs.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

No Feasible Interpolation for TC0-Frege Proofs.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Resolution and the Weak Pigeonhole Principle.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996
The future of computational complexity theory: part II.
SIGACT News, 1996

An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.
Ann. Pure Appl. Log., 1996

Simplified and Improved Resolution Lower Bounds.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Algebraic Propositional Proof Systems.
Proceedings of the Descriptive Complexity and Finite Models, 1996

Towards lower bounds for bounded-depth Frege proofs with modular connectives.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995
The Complexity of the Hajos Calculus.
SIAM J. Discret. Math., 1995

Exponential Lower Bounds for the Tree-Like Hajós Calculus.
Inf. Process. Lett., 1995

Improved Depth Lower Vounds for Small Distance Connectivity.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Upper and Lower Bounds for Tree-Like Cutting Planes Proofs
Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94), 1994

Lower Bound on Hilbert's Nullstellensatz and propositional proofs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Semantics of Nondeterministic Asynchronous Broadcast Networks
Inf. Comput., June, 1993

Exponential Lower Bounds for the Pigeonhole Principle.
Comput. Complex., 1993

An Exponential Separation between the Matching Principle and the Pigeonhole Principle
Proceedings of the Eighth Annual Symposium on Logic in Computer Science (LICS '93), 1993

1992
Approximation and Small-Depth Frege Proofs.
SIAM J. Comput., 1992

Exponential Lower Bounds for the Pigeonhole Principle
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1990
A Feasibly Constructive Lower Bound for Resolution Proofs.
Inf. Process. Lett., 1990


  Loading...