Toniann Pitassi

CoRR, 2012

A little advice can be very helpful.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Jeff Edmonds

Faith Ellen

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

Fairness through awareness.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Communication Complexity and Information Complexity: Foundations and New Directions.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

The Hardness of Being Private.

[BibT_eX]

[DOI]

Anil Ada

Arkadev Chattopadhyay

Proceedings of the 27th Conference on Computational Complexity, 2012

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

[BibT_eX]

[DOI]

Per Austrin

Yu Wu

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

2011

Special Issue In Memory of Misha Alekhnovich. Foreword.

[BibT_eX]

[DOI]

Allan Borodin

Alexander A. Razborov

Comput. Complex., 2011

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

[BibT_eX]

[DOI]

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

Automatizability and Simple Stochastic Games.

[BibT_eX]

[DOI]

Lei Huang

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

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds.

[BibT_eX]

[DOI]

Yuval Filmus

Rahul Santhanam

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

2010

Separating Deterministic from Randomized Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Theory Comput., 2010

The story of set disjointness.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

SIGACT News, 2010

The PSPACE-Completeness of Black-White Pebbling.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

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

[BibT_eX]

[DOI]

Konstantinos Georgiou

Iannis Tourlakis

SIAM J. Comput., 2010

Differential privacy under continual observation.

[BibT_eX]

[DOI]

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

Hardness amplification in proof complexity.

[BibT_eX]

[DOI]

Trinh Huynh

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

Effectively Polynomial Simulations.

[BibT_eX]

[DOI]

Rahul Santhanam

Proceedings of the Innovations in Computer Science, 2010

Pan-Private Streaming Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2010

The Limits of Two-Party Differential Privacy.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Solving #SAT and Bayesian Inference with Backtracking Search.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2009

Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.

[BibT_eX]

[DOI]

Nathan Segerlind

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.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

The complexity of properly learning simple concept classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Separating NOF communication complexity classes RP and NP.

[BibT_eX]

[DOI]

Matei David

Electron. Colloquium Comput. Complex., 2008

Improved Separations between Nondeterministic and Randomized Multiparty Communication.

[BibT_eX]

[DOI]

Matei David

Emanuele Viola

Proceedings of the Approximation, 2008

Clause Learning Can Effectively P-Simulate General Propositional Resolution.

[BibT_eX]

[DOI]

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

2007

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

[BibT_eX]

[DOI]

Nathan Segerlind

SIAM J. Comput., 2007

An Exponential Time/Space Speedup For Resolution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Black-White Pebbling is PSPACE-Complete.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Konstantinos Georgiou

Iannis Tourlakis

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

2006

Rank Bounds and Integrality Gaps for Cutting Planes Procedures.

[BibT_eX]

[DOI]

Joshua Buresh-Oppenheim

Theory Comput., 2006

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

[BibT_eX]

[DOI]

Konstantinos Georgiou

Iannis Tourlakis

Electron. Colloquium Comput. Complex., 2006

Formula Caching in DPLL.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

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

[BibT_eX]

[DOI]

Comput. Complex., 2006

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

[BibT_eX]

[DOI]

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

Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.

[BibT_eX]

[DOI]

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

Monotone Circuits for the Majority Function.

[BibT_eX]

[DOI]

Shlomo Hoory

Proceedings of the Approximation, 2006

2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.

[BibT_eX]

[DOI]

Nathan Segerlind

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.

[BibT_eX]

[DOI]

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

Toward a Model for Backtracking and Dynamic Programming.

[BibT_eX]

[DOI]

Michael Alekhnovich

Allan Borodin

Joshua Buresh-Oppenheim

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

2004

Combining Component Caching and Clause Learning for Effective Model Counting.

[BibT_eX]

[DOI]

Proceedings of the SAT 2004, 2004

Learnability and Automatizability.

[BibT_eX]

[DOI]

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

2003

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Value Elimination: Bayesian Interence via Backtracking Search.

[BibT_eX]

[DOI]

Proceedings of the UAI '03, 2003

The Complexity of Resolution Refinements.

[BibT_eX]

[DOI]

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.

[BibT_eX]

[DOI]

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

Algorithms and Complexity Results for #SAT and Bayesian Inference.

[BibT_eX]

[DOI]

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

Memoization and DPLL: Formula Caching Proof Systems.

[BibT_eX]

[DOI]

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

2002

The Efficiency of Resolution and Davis--Putnam Procedures.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Homogenization and the polynomial calculus.

[BibT_eX]

[DOI]

Matthew Clegg

Comput. Complex., 2002

An exponential separation between regular and general resolution.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Stochastic Boolean Satisfiability.

[BibT_eX]

[DOI]

Michael L. Littman

Stephen M. Majercik

J. Autom. Reason., 2001

Linear and Negative Resolution are Weaker than Resolution

[BibT_eX]

[DOI]

David G. Mitchell

Electron. Colloquium Comput. Complex., 2001

Regular resolution lower bounds for the weak pigeonhole principle.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

The complexity of analytic tableaux.

[BibT_eX]

[DOI]

Noriko H. Arai

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Propositional Proof Complexity: Past, Present, and Future.

[BibT_eX]

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

On Interpolation and Automatization for Frege Systems.

[BibT_eX]

[DOI]

Maria Luisa Bonet

SIAM J. Comput., 2000

A new proof of the weak pigeonhole principle.

[BibT_eX]

[DOI]

Alan R. Woods

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

A Gradient-Based Boosting Algorithm for Regression Problems.

[BibT_eX]

[DOI]

Richard S. Zemel

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

Homogenization and the Polynominal Calculus.

[BibT_eX]

[DOI]

Matthew Clegg

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

1999

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

[BibT_eX]

[DOI]

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).

[BibT_eX]

[DOI]

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

Non-Automatizability of Bounded-Depth Frege Proofs.

[BibT_eX]

[DOI]

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

1998

Propositional Proof Complexity: Past, Present and Future

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Improved Depth Lower Bounds for Small Distance Connectivity.

[BibT_eX]

[DOI]

Comput. Complex., 1998

On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

On ACC0[pk] Frege Proofs.

[BibT_eX]

[DOI]

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

Reducing the Complexity of Reductions.

[BibT_eX]

[DOI]

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

No Feasible Interpolation for TC0-Frege Proofs.

[BibT_eX]

[DOI]

Maria Luisa Bonet

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

Resolution and the Weak Pigeonhole Principle.

[BibT_eX]

[DOI]

Samuel R. Buss

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

1996

The future of computational complexity theory: part II.

[BibT_eX]

[DOI]

SIGACT News, 1996

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

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 1996

Simplified and Improved Resolution Lower Bounds.

[BibT_eX]

[DOI]

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

Algebraic Propositional Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the Descriptive Complexity and Finite Models, 1996

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

[BibT_eX]

[DOI]

Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.

[BibT_eX]

[DOI]

Samuel R. Buss

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

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

[BibT_eX]

[DOI]

Kazuo Iwama

Inf. Process. Lett., 1995

Lower bounds for cutting planes proofs with small coefficients.

[BibT_eX]

[DOI]

Maria Luisa Bonet

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

The relative complexity of NP search problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved Depth Lower Vounds for Small Distance Connectivity.

[BibT_eX]

[DOI]

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

1994

Upper and Lower Bounds for Tree-Like Cutting Planes Proofs

[BibT_eX]

[DOI]

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

Lower Bound on Hilbert's Nullstellensatz and propositional proofs

[BibT_eX]

[DOI]

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

1993

Exponential Lower Bounds for the Pigeonhole Principle.

[BibT_eX]

[DOI]

Comput. Complex., 1993

An Exponential Separation between the Matching Principle and the Pigeonhole Principle

[BibT_eX]

[DOI]

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

1992

The power of weak formal systems.

[BibT_eX]

[DOI]

PhD thesis, 1992

Exponential Lower Bounds for the Pigeonhole Principle

[BibT_eX]

[DOI]

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

The Complexity of the Hajós Calculus

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Approximation and Small Depth Frege Proofs.

[BibT_eX]

[DOI]

Stephen J. Bellantoni

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.

[BibT_eX]

[DOI]

Stephen A. Cook

Inf. Process. Lett., 1990

1987

Semantics for Nondeterministic Asynchronous Broadcast Networks.

[BibT_eX]

[DOI]

R. K. Shyamasundar

K. T. Narayana