Toniann Pitassi

According to our database1, Toniann Pitassi authored at least 185 papers between 1987 and 2018.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Randomized Communication versus Partition Number.
TOCT, 2018

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

Learning Adversarially Fair and Transferable Representations.
CoRR, 2018

The Landscape of Communication Complexity Classes.
Computational Complexity, 2018

Lifting nullstellensatz to monotone span programs over any field.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Stabbing Planes.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Learning Adversarially Fair and Transferable Representations.
Proceedings of the 35th International Conference on Machine Learning, 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

Query-to-Communication Lifting for P^NP.
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

Predict Responsibly: Increasing Fairness by Learning To Defer.
CoRR, 2017

Stabbing Planes.
CoRR, 2017

Query-to-Communication Lifting for BPP.
CoRR, 2017

Random CNFs are Hard for Cutting Planes.
CoRR, 2017

Guilt-free data reuse.
Commun. ACM, 2017

Strongly exponential lower bounds for monotone computation.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Randomized Communication vs. Partition Number.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Query-to-Communication Lifting for BPP.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

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

Query-to-Communication Lifting for P^NP.
Proceedings of the 32nd Computational Complexity Conference, 2017

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

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

Algebraic Proof Complexity: Progress, Frontiers and Challenges.
Electronic Colloquium on Computational Complexity (ECCC), 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

Algebraic Proof Complexity: Progress, Frontiers and Challenges.
CoRR, 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

The Landscape of Communication Complexity Classes.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

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

Exponential Lower Bounds for Monotone Span Programs.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds.
TOCT, 2015

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

The Landscape of Communication Complexity Classes.
Electronic Colloquium on Computational Complexity (ECCC), 2015

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

Generalization in Adaptive Data Analysis and Holdout Reuse.
CoRR, 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

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Inapproximability of Treewidth and Related Problems (Extended Abstract).
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Deterministic Communication vs. Partition Number.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
The Hardness of Being Private.
TOCT, 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

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Circuit complexity, proof complexity, and polynomial identity testing.
CoRR, 2014

Preserving Statistical Validity in Adaptive Data Analysis.
CoRR, 2014

Solving #SAT and Bayesian Inference with Backtracking Search.
CoRR, 2014

Lifting lower bounds for tree-like proofs.
Computational Complexity, 2014

Communication lower bounds via critical block sensitivity.
Proceedings of the Symposium on Theory of Computing, 2014

Circuit Complexity, Proof Complexity, and Polynomial Identity Testing.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 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

Communication Lower Bounds via Critical Block Sensitivity.
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

Average Case Lower Bounds for Monotone Switching Networks.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 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
Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures.
SIAM J. Comput., 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

The Hardness of Being Private.
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

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

Fairness Through Awareness
CoRR, 2011

Special Issue In Memory of Misha Alekhnovich. Foreword.
Computational Complexity, 2011

Toward a Model for Backtracking and Dynamic Programming.
Computational Complexity, 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

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Formula Caching in DPLL.
TOCT, 2010

Separating Deterministic from Randomized Multiparty Communication Complexity.
Theory of Computing, 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

The Limits of Two-Party Differential Privacy.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Improved Separations between Nondeterministic and Randomized Multiparty Communication.
TOCT, 2009

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

Hardness Amplification in Proof Complexity
CoRR, 2009

Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Minimizing Disjunctive Normal Form Formulas and AC0 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

Separating NOF communication complexity classes RP and NP
CoRR, 2008

Improved Separations between Nondeterministic and Randomized Multiparty Communication.
Proceedings of the Approximation, 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 of Computing, 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 of Computing, 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.
Computational Complexity, 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 AC0d 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

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 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

Toward a Model for Backtracking and Dynamic Programming.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
SIAM J. Comput., 2004

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

Non-Automatizability of Bounded-Depth Frege Proofs.
Computational Complexity, 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

The Complexity of Resolution Refinements.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 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.
Computational Complexity, 2002

An exponential separation between regular and general resolution.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 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

An Exponential Separation between Regular and General Resolution
Electronic Colloquium on Computational Complexity (ECCC), 2001

Reducing the complexity of reductions.
Computational Complexity, 2001

Regular resolution lower bounds for the weak pigeonhole principle.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

The complexity of analytic tableaux.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

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

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

A new proof of the weak pigeonhole principle.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 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.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

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

Non-Automatizability of Bounded-Depth Frege Proofs.
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

Propositional Proof Complexity: Past, Present and Future.
Bulletin of the EATCS, 1998

Improved Depth Lower Bounds for Small Distance Connectivity.
Computational Complexity, 1998

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

Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

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

On ACC0[pk] Frege Proofs.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Reducing the Complexity of Reductions.
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. Logic, 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

Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

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

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

Lower bounds for cutting planes proofs with small coefficients.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

The relative complexity of NP search problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 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.
Computational Complexity, 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

The Complexity of the Hajós Calculus
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Approximation and Small Depth Frege Proofs.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

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

1987
Semantics for Nondeterministic Asynchronous Broadcast Networks.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987


  Loading...