R. Ryan Williams

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

On the parameterized complexity of k-SUM.

[BibT_eX]

[DOI]

Amir Abboud

Kevin Lewi

CoRR, 2013

Natural proofs versus derandomization.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Massive online teaching to bounded learners.

[BibT_eX]

[DOI]

Brendan Juba

Proceedings of the Innovations in Theoretical Computer Science, 2013

Towards NEXP versus BPP?

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2013

On Medium-Uniformity and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

SIGACT News, 2012

Uniform Circuits, Lower Bounds, and QBF Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

An Atypical Survey of Typical-Case Heuristic Algorithms

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

CoRR, 2012

Amplifying Circuit Lower Bounds against Polynomial Time with Applications.

[BibT_eX]

[DOI]

Richard J. Lipton

Proceedings of the 27th Conference on Computational Complexity, 2012

Limits on Alternation-Trading Proofs for Time-Space Lower Bounds.

[BibT_eX]

[DOI]

Samuel R. Buss

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Guest column: a casual tour around a circuit complexity bound.

[BibT_eX]

[DOI]

SIGACT News, 2011

A Casual Tour Around a Circuit Complexity Bound

[BibT_eX]

[DOI]

CoRR, 2011

Connecting SAT Algorithms and Complexity Lower Bounds.

[BibT_eX]

[DOI]

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

Maximizing conjunctive views in deletion propagation.

[BibT_eX]

[DOI]

Benny Kimelfeld

Jan Vondrák

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Improved Parameterized Algorithms for above Average Constraint Satisfaction.

[BibT_eX]

[DOI]

Eun Jung Kim

Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

Non-uniform ACC Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Finding heaviest H-subgraphs in real weighted graphs, with applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Improved Parameterized Algorithms for Constraint Satisfaction

[BibT_eX]

[DOI]

Eun Jung Kim

CoRR, 2010

Improving exhaustive search implies superpolynomial lower bounds.

[BibT_eX]

[DOI]

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

Alternation-Trading Proofs, Linear Programming, and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

On the Possibility of Faster SAT Algorithms.

[BibT_eX]

[DOI]

Mihai Patrascu

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Resolving the Complexity of Some Data Privacy Problems.

[BibT_eX]

[DOI]

Jeremiah Blocki

Virginia Vassilevska Williams

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Subcubic Equivalences between Path, Matrix and Triangle Problems.

[BibT_eX]

[DOI]

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

Communication Complexity with Synchronized Clocks.

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time.

[BibT_eX]

[DOI]

Theory Comput., 2009

Finding paths of length k in O*(2k) time.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

Finding, minimizing, and counting weighted subgraphs.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Limits and Applications of Group Algebras for Parameterized Problems.

[BibT_eX]

[DOI]

Ioannis Koutis

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Regularity Lemmas and Combinatorial Algorithms.

[BibT_eX]

[DOI]

Nikhil Bansal

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

An Improved Time-Space Lower Bound for Tautologies.

[BibT_eX]

[DOI]

Scott Diehl

Dieter van Melkebeek

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

Fixed-Polynomial Size Circuit Bounds.

[BibT_eX]

[DOI]

Lance Fortnow

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Maximum Two-Satisfiability.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Applying practice to theory.

[BibT_eX]

[DOI]

SIGACT News, 2008

Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Finding paths of length k in O*(2^k) time

[BibT_eX]

[DOI]

CoRR, 2008

A New Combinatorial Approach for Sparse Graph Problems.

[BibT_eX]

[DOI]

Guy E. Blelloch

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

08431 Open Problems - Moderately Exponential Time Algorithms.

[BibT_eX]

[DOI]

Johan M. M. van Rooij

Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

2007

All-pairs bottleneck paths for general graphs in truly sub-cubic time.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Matrix-vector multiplication in sub-quadratic time: (some preprocessing required).

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Finding heaviest H-subgraphs in real weighted graphs, with applications

[BibT_eX]

[DOI]

CoRR, 2006

Inductive Time-Space Lower Bounds for Sat and Related Problems.

[BibT_eX]

[DOI]

Comput. Complex., 2006

Finding a maximum weight triangle in n3-Delta time, with applications.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Confronting hardness using a hybrid approach.

[BibT_eX]

[DOI]

Shan Leung Maverick Woo

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Finding Small Unsatisfiable Cores to Prove Unsatisfiability of QBFs.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2006

Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

A new algorithm for optimal 2-constraint satisfaction and its implications.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Parallelizing time with polynomial circuits.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Better Time-Space Lower Bounds for SAT and Related Problems.

[BibT_eX]

[DOI]

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

2004

On the Complexity of Optimal K-Anonymity.

[BibT_eX]

[DOI]

Adam Meyerson

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

A New Algorithm for Optimal Constraint Satisfaction and Its Implications.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

On Computing k-CNF Formula Properties.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2003

Backdoors To Typical Case Complexity.

[BibT_eX]

[DOI]

Carla P. Gomes

Bart Selman

Proceedings of the IJCAI-03, 2003

2002

Algorithms for quantified Boolean formulas.

[BibT_eX]

[DOI]