Dieter van Melkebeek

Nicollas M. Sdroievski

Comput. Complex., December, 2025

From Dynamic Programs to Greedy Algorithms.

[BibT_eX]

[DOI]

CoRR, August, 2025

2024

Lower Bound Techniques in the Comparison-Query Model and Applications to Inversion Minimization.

[BibT_eX]

[DOI]

Ivan Hu

Theory Comput., 2024

Polynomial Identity Testing via Evaluation of Rational Functions.

[BibT_eX]

[DOI]

Ivan Hu

Theory Comput., 2024

2023

Query Complexity of Inversion Minimization on Trees.

[BibT_eX]

[DOI]

Ivan Hu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols.

[BibT_eX]

[DOI]

Nicollas M. Sdroievski

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols.

[BibT_eX]

[DOI]

Nicollas M. Sdroievski

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Polynomial Identity Testing via Evaluation of Rational Functions.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2018

Minimum Circuit Size, Graph Isomorphism, and Related Problems.

[BibT_eX]

[DOI]

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

2017

Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games.

[BibT_eX]

[DOI]

Baris Aydinlioglu

Comput. Complex., 2017

Derandomizing Isolation in Space-Bounded Settings.

[BibT_eX]

[DOI]

Gautam Prakriya

Proceedings of the 32nd Computational Complexity Conference, 2017

2015

Deterministic polynomial identity tests for multilinear bounded-read formulae.

[BibT_eX]

[DOI]

Matthew Anderson

Ilya Volkovich

Comput. Complex., 2015

2012

On derandomization and average-case complexity of monotone functions.

[BibT_eX]

[DOI]

George Karakostas

Theor. Comput. Sci., 2012

Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011).

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Ronen Shaltiel

Comput. Complex., 2012

Is Valiant-Vazirani's Isolation Probability Improvable?

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games.

[BibT_eX]

[DOI]

Baris Aydinlioglu

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

On Circuit Lower Bounds from Derandomization.

[BibT_eX]

[DOI]

Scott Aaronson

Theory Comput., 2011

Locality from Circuit Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2011

Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates.

[BibT_eX]

[DOI]

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

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.

[BibT_eX]

[DOI]

Matthew Anderson

Ilya Volkovich

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

2010

Time-Space Efficient Simulations of Quantum Computations.

[BibT_eX]

[DOI]

Thomas Watson

Electron. Colloquium Comput. Complex., 2010

A note on circuit lower bounds from derandomization.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2010

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Space Hierarchy Results for Randomized and other Semantic Models.

[BibT_eX]

[DOI]

Comput. Complex., 2010

2009

Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006).

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses.

[BibT_eX]

[DOI]

Holger Dell

Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

An Improved Time-Space Lower Bound for Tautologies.

[BibT_eX]

[DOI]

Scott Diehl

Ryan Williams

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

Pseudorandom Generators and Typically-Correct Derandomization.

[BibT_eX]

[DOI]

Ronen Shaltiel

Proceedings of the Approximation, 2009

2008

A Quantum Time-Space Lower Bound for the Counting Hierarchy.

[BibT_eX]

[DOI]

Thomas Watson

Electron. Colloquium Comput. Complex., 2008

Space Hierarchy Results for Randomized Models.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008

08381 Executive Summary - Computational Complexity of Discrete Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

08381 Abstracts Collection - Computational Complexity of Discrete Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

2007

A Generic Time Hierarchy with One Bit of Advice.

[BibT_eX]

[DOI]

Konstantin Pervyshev

Comput. Complex., 2007

2006

Computational depth: Concept and applications.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

A Survey of Lower Bounds for Satisfiability and Related Problems.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2006

06111 Abstracts Collection -- Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

06111 Executive Summary -- Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.

[BibT_eX]

[DOI]

Scott Diehl

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

A Generic Time Hierarchy for Semantic Models with One Bit of Advice.

[BibT_eX]

[DOI]

Konstantin Pervyshev

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

2005

Holographic Proofs and Derandmization.

[BibT_eX]

[DOI]

Venkatesan T. Chakaravarthy

Rahul Santhanam

SIAM J. Comput., 2005

Time-space lower bounds for satisfiability.

[BibT_eX]

[DOI]

J. ACM, 2005

2004

Time-Space Tradeoff in Derandomizing Probabilistic Logspace.

[BibT_eX]

[DOI]

Jin-yi Cai

Proceedings of the STACS 2004, 2004

A Time Lower Bound for Satisfiability.

[BibT_eX]

[DOI]

Ran Raz

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

Language Compression and Pseudorandom Generators.

[BibT_eX]

[DOI]

Harry Buhrman

Troy Lee

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Holographic Proofs and Derandomization.

[BibT_eX]

[DOI]

Rahul Santhanam

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

2002

The Quantum Black-Box Complexity of Majority.

[BibT_eX]

[DOI]

Thomas P. Hayes

Samuel Kutin

Algorithmica, 2002

Power from Random Strings.

[BibT_eX]

[DOI]

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

2001

The Computational Complexity Column Time-Space Lower Bounds for Satisfiability.

[BibT_eX]

Bull. EATCS, 2001

Computational Depth.

[BibT_eX]

[DOI]

Luis Antunes

Lance Fortnow

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

The zero-one law holds for BPP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Separating Complexity Classes Using Autoreducibility.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Optimal Proof Systems and Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Time-Space Tradeoffs for Nondeterministic Computation.

[BibT_eX]

[DOI]

Lance Fortnow

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

Randomness and Completeness in Computational Complexity

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 1950, Springer, ISBN: 3-540-41492-4, 2000

1999

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

[BibT_eX]

[DOI]

Adam R. Klivans

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the STACS 98, 1998

Hard Sets are Hard to Find.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Sparse Hard Sets for P.

[BibT_eX]

Mitsunori Ogihara

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L.

[BibT_eX]

[DOI]