Harry Buhrman

François Le Gall

Jordi Weggemans

CoRR, 2024

Beating Grover search for low-energy estimation and state preparation.

[BibT_eX]

[DOI]

CoRR, 2024

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians.

[BibT_eX]

[DOI]

Jonas Helsen

Jordi Weggemans

CoRR, 2024

Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem.

[BibT_eX]

[DOI]

Scott Aaronson

William Kretschmer

Electron. Colloquium Comput. Complex., 2023

Noisy decoding by shallow circuits with parities: classical and quantum.

[BibT_eX]

[DOI]

CoRR, 2023

Quantum Majority Vote.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture.

[BibT_eX]

[DOI]

CoRR, 2022

Memory Compression with Quantum Random-Access Gates.

[BibT_eX]

[DOI]

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks.

[BibT_eX]

[DOI]

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

2021

High Entropy Random Selection Protocols.

[BibT_eX]

[DOI]

Algorithmica, 2021

A Framework of Quantum Strong Exponential-Time Hypotheses.

[BibT_eX]

[DOI]

Subhasree Patro

Florian Speelman

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2019

The Quantum Strong Exponential-Time Hypothesis.

[BibT_eX]

[DOI]

Subhasree Patro

Florian Speelman

CoRR, 2019

Bounding Quantum-Classical Separations for Classes of Nonlocal Games.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Catalytic Space: Non-determinism and Hierarchy.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

The Case for Quantum Software.

[BibT_eX]

[DOI]

Floor van de Pavert

ERCIM News, 2018

2017

Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication.

[BibT_eX]

[DOI]

Luis Filipe Coelho Antunes

Matthias Christandl

Jeroen Zuiddam

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Distinguishing Two Probability Ensembles with One Sample from each Ensemble.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

Entanglement-Assisted Zero-Error Source-Channel Coding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2015

Hardness of Approximation for Knapsack Problems.

[BibT_eX]

[DOI]

Bruno Loff

Theory Comput. Syst., 2015

Round Elimination in Exact Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 10th Conference on the Theory of Quantum Computation, 2015

2014

Position-Based Quantum Cryptography: Impossibility and Constructions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Computing with a full memory: Catalytic space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

On the Parallel Repetition of Multi-Player Games: The No-Signaling Case.

[BibT_eX]

[DOI]

Serge Fehr

Christian Schaffner

Proceedings of the 9th Conference on the Theory of Quantum Computation, 2014

Turing in Quantumland.

[BibT_eX]

[DOI]

Proceedings of the Turing's Legacy: Developments from Turing's Ideas in Logic, 2014

2013

Multipartite entanglement in XOR games.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2013

The non-adaptive query complexity of testing k-parities.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2013

Learning Reductions to Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

The garden-hose model.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Near-Optimal and Explicit Bell Inequality Violations.

[BibT_eX]

[DOI]

Theory Comput., 2012

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Reductions to the set of random strings: the resource-bounded case.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Violating the Shannon capacity of metric graphs with entanglement

[BibT_eX]

[DOI]

Jop Briët

Dion Gijswijt

CoRR, 2012

Complete Insecurity of Quantum Protocols for Classical Two-Party Computation

[BibT_eX]

[DOI]

Matthias Christandl

Christian Schaffner

CoRR, 2012

2011

Some Mathematical Refinements Concerning Error Minimization in the Genetic Code.

[BibT_eX]

[DOI]

Peter T. S. van der Gulik

Steven Kelk

Wouter M. Koolen

Leen Stougie

IEEE ACM Trans. Comput. Biol. Bioinform., 2011

Position-Based Quantum Cryptography.

[BibT_eX]

[DOI]

Serge Fehr

Christian Schaffner

ERCIM News, 2011

The Garden-Hose Game: A New Model of Computation, and Application to Position-Based Quantum Cryptography

[BibT_eX]

[DOI]

CoRR, 2011

2010

Non-Uniform Reductions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Learning parities in the mistake-bound model.

[BibT_eX]

[DOI]

David García-Soriano

Arie Matsliah

Inf. Process. Lett., 2010

Sparse Selfreducible Sets and Nonuniform Lower Bounds.

[BibT_eX]

[DOI]

Falk Unger

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

Derandomizing from Random Strings.

[BibT_eX]

[DOI]

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

2009

Unconditional Lower Bounds against Advice.

[BibT_eX]

[DOI]

Rahul Santhanam

Electron. Colloquium Comput. Complex., 2009

2008

Quantum Property Testing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Foreword.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly.

[BibT_eX]

[DOI]

John M. Hitchcock

Electron. Colloquium Comput. Complex., 2008

Randomised Individual Communication Complexity.

[BibT_eX]

[DOI]

Michal Koucký

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly.

[BibT_eX]

[DOI]

John M. Hitchcock

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Robust Polynomials and Quantum Algorithms.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Individual communication complexity.

[BibT_eX]

[DOI]

Hartmut Klauck

J. Comput. Syst. Sci., 2007

Quantum Information Processing.

[BibT_eX]

[DOI]

Bram Vermeer

ERCIM News, 2007

On Computation and Communication with Small Bias.

[BibT_eX]

[DOI]

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2007

07411 Abstracts Collection -- Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

07411 Executive Summary -- Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

Inverting Onto Functions and Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2007

On Computation and Communication with Small Bias.

[BibT_eX]

[DOI]

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

2006

Power from Random Strings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Enumerations of the Kolmogorov function.

[BibT_eX]

[DOI]

J. Symb. Log., 2006

Inverting onto functions might not be hard.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On the importance of having an identity or, is consensus really universal?.

[BibT_eX]

[DOI]

Distributed Comput., 2006

Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds.

[BibT_eX]

[DOI]

Falk Unger

Proceedings of the STACS 2006, 2006

Quantum verification of matrix products.

[BibT_eX]

[DOI]

Robert Spalek

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

New Limits on Fault-Tolerant Quantum Computation.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Quantum Algorithms for Element Distinctness.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Some Results on Derandomization.

[BibT_eX]

[DOI]

Aduri Pavan

Theory Comput. Syst., 2005

A Post's Program for Complexity Theory.

[BibT_eX]

Bull. EATCS, 2005

Language compression and pseudorandom generators.

[BibT_eX]

[DOI]

Troy Lee

Dieter van Melkebeek

Comput. Complex., 2005

Quantum Computing.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

2004

Increasing Kolmogorov Complexity

[BibT_eX]

[DOI]

Ilan Newman

Electron. Colloquium Comput. Complex., 2004

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

[BibT_eX]

[DOI]

Eric Allender

Michal Koucký

Electron. Colloquium Comput. Complex., 2004

Individual Communication Complexity: Extended Abstract.

[BibT_eX]

[DOI]

Hartmut Klauck

Proceedings of the STACS 2004, 2004

What Can be Efficiently Reduced to the K-Random Strings?

[BibT_eX]

[DOI]

Eric Allender

Michal Koucký

Proceedings of the STACS 2004, 2004

04421 Abstracts Collection - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

Separating Complexity Classes Using Structural Properties.

[BibT_eX]

[DOI]

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

Multiparty Quantum Coin Flipping.

[BibT_eX]

[DOI]

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

2003

Quantum zero-error algorithms cannot be composed.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

Robust Quantum Algorithms and Polynomials

[BibT_eX]

[DOI]

CoRR, 2003

One Bit of Advice.

[BibT_eX]

[DOI]

Richard Chang

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Distributed Quantum Computing.

[BibT_eX]

[DOI]

Hein Röhrig

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002

Complexity measures and decision tree complexity: a survey.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Are Bitvectors Optimal?

[BibT_eX]

[DOI]

Peter Bro Miltersen

Jaikumar Radhakrishnan

Srinivasan Venkatesh

SIAM J. Comput., 2002

2001

Compressibility and Resource Bounded Measure.

[BibT_eX]

[DOI]

Luc Longpré

SIAM J. Comput., 2001

Resource-Bounded Kolmogorov Complexity Revisited.

[BibT_eX]

[DOI]

Sophie Laplante

SIAM J. Comput., 2001

The Communication Complexity of Enumeration, Elimination, and Selection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Quantum lower bounds by polynomials.

[BibT_eX]

[DOI]

J. ACM, 2001

Two oracles that force a big crunch.

[BibT_eX]

[DOI]

Comput. Complex., 2001

Time and Space Bounds for Reversible Simulation.

[BibT_eX]

[DOI]

John Tromp

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Communication Complexity Lower Bounds by Polynomials.

[BibT_eX]

[DOI]

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

Quantum Computing and Communication Complexity.

[BibT_eX]

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

New applications of the incompressibility method: Part II.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Randomness is Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Separating Complexity Classes Using Autoreducibility.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Quantum Entanglement and Communication Complexity.

[BibT_eX]

[DOI]

Richard Cleve

Wim van Dam

SIAM J. Comput., 2000

Quantum Computing and Communication Complexity.

[BibT_eX]

Bull. EATCS, 2000

Optimal Proof Systems and Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

New Bounds for the Language Compression Problem.

[BibT_eX]

[DOI]

Sophie Laplante

Peter Bro Miltersen

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

1999

Kolmogorov Random Graphs and the Incompressibility Method.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method.

[BibT_eX]

[DOI]

Jaap-Henk Hoepman

SIAM J. Comput., 1999

Hard Sets Are Hard to Find.

[BibT_eX]

[DOI]

Dieter van Melkebeek

J. Comput. Syst. Sci., 1999

Two Queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Mutual Search.

[BibT_eX]

[DOI]

J. ACM, 1999

A Lower Bound for Quantum Search of an Ordered List.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

One-sided Versus Two-sided Error in Probabilistic Computation.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

New Applications of the Incompressibility Method.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

Bounds for Small-Error and Zero-Error Quantum Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Complicated Complementations.

[BibT_eX]

[DOI]

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

Quantum Bounded Query Complexity.

[BibT_eX]

[DOI]

Wim van Dam

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

1998

Splittings, Robustness, and Structure of Complete Sets.

[BibT_eX]

[DOI]

Albrecht Hoene

SIAM J. Comput., 1998

Functions Computable with Nonadaptive Queries to NP.

[BibT_eX]

[DOI]

Jim Kadin

Theory Comput. Syst., 1998

Lower Bounds for Quantum Search and Derandomization

[BibT_eX]

[DOI]

CoRR, 1998

Quantum vs. Classical Communication and Computation.

[BibT_eX]

[DOI]

Richard Cleve

Avi Wigderson

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

NP Might Not Be As Easy As Detecting Unique Solutions.

[BibT_eX]

[DOI]

Richard Beigel

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

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

[BibT_eX]

[DOI]

Proceedings of the STACS 98, 1998

Mutual Search (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Nonrelativizing Separations.

[BibT_eX]

[DOI]

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

1997

An Excursion to the Kolmogorov Random Strings.

[BibT_eX]

[DOI]

Elvira Mayordomo

J. Comput. Syst. Sci., 1997

Resource-Bounded Kolmogorov Complexity Revisited.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Kolmogorov random graphs.

[BibT_eX]

[DOI]

Ming Li

Proceedings of the Compression and Complexity of SEQUENCES 1997, 1997

Results on Resource-Bounded Measure.

[BibT_eX]

[DOI]

Stephen A. Fenner

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Six Hypotheses in Search of a Theorem.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

A short note on Shor's factoring algorithm.

[BibT_eX]

[DOI]

SIGACT News, 1996

P-Selektive Self-Reducible Sets: A New Characterization of P.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

Random Strings Make Hard Instances.

[BibT_eX]

[DOI]

Pekka Orponen

J. Comput. Syst. Sci., 1996

The Complexity of Generating and Checking Proffs of Membership.

[BibT_eX]

[DOI]

Proceedings of the STACS 96, 1996

Optimal Routing Tables.

[BibT_eX]

[DOI]

Jaap-Henk Hoepman

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

1995

SPARSE Reduces Conjunctively to TALLY.

[BibT_eX]

[DOI]

Edith Hemaspaandra

Luc Longpré

SIAM J. Comput., 1995

On the Sparse Set Conjecture for Sets with Low Denisty.

[BibT_eX]

[DOI]

Montserrat Hermo

Proceedings of the STACS 95, 1995

Long-Lived Renaming Made Fast.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Optimal Resiliency against Mobile Faults.

[BibT_eX]

[DOI]

Juan A. Garay

Jaap-Henk Hoepman

Proceedings of the Digest of Papers: FTCS-25, 1995

Using Autoreducibility to Separate Complexity Classes.

[BibT_eX]

[DOI]

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

Learnability of Kolmogorov-easy circuit expressions via queries.

[BibT_eX]

[DOI]

José L. Balcázar

Montserrat Hermo

Proceedings of the Computational Learning Theory, Second European Conference, 1995

1994

On the Cutting Edge of Relativization: The Resource Bounded Injury Method.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

On the Structure of Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Twenty Questions to a P-Selector.

[BibT_eX]

[DOI]

Peter van Emde Boas

Inf. Process. Lett., 1993

The Relative Power of Logspace and Polynomial Time Reductions.

[BibT_eX]

[DOI]

Edith Spaan

Comput. Complex., 1993

P-Selective Self-reducibles Sets: A New Characterization of <i>P</i>.

[BibT_eX]

[DOI]

Peter van Helden

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy.

[BibT_eX]

[DOI]

Steven Homer

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

1991

Completeness for Nondeterministic Complexity Classes.

[BibT_eX]

[DOI]

Steven Homer

Math. Syst. Theory, 1991

Bounded Reductions.

[BibT_eX]

[DOI]

Edith Spaan