Bounded Reductions. - Harry Buhrman; Edith Spaan; Leen Torenvliet (STACS, 1991)

Completeness for Nondeterministic Complexity Classes. - Harry Buhrman; Steven Homer; Leen Torenvliet (Math. Syst. Theory, 1991)

Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. - Harry Buhrman; Steven Homer (FSTTCS, 1992)

P-Selective Self-reducibles Sets: A New Characterization of P. - Harry Buhrman; Peter van Helden; Leen Torenvliet (SCT, 1993)

The Relative Power of Logspace and Polynomial Time Reductions. - Harry Buhrman; Edith Spaan; Leen Torenvliet (Comput. Complex., 1993)

Twenty Questions to a P-Selector. - Harry Buhrman; Leen Torenvliet; Peter van Emde Boas (Inf. Process. Lett., 1993)

On the Structure of Complete Sets. - Harry Buhrman; Leen Torenvliet (SCT, 1994)

On the Cutting Edge of Relativization: The Resource Bounded Injury Method. - Harry Buhrman; Leen Torenvliet (ICALP, 1994)

Learnability of Kolmogorov-easy circuit expressions via queries. - José L. Balcázar; Harry Buhrman; Montserrat Hermo (EuroCOLT, 1995)

Using Autoreducibility to Separate Complexity Classes. - Harry Buhrman; Lance Fortnow; Leen Torenvliet (FOCS, 1995)

Optimal Resiliency against Mobile Faults. - Harry Buhrman; Juan A. Garay; Jaap-Henk Hoepman (FTCS, 1995)

Long-Lived Renaming Made Fast. - Harry Buhrman; Juan A. Garay; Jaap-Henk Hoepman; Mark Moir (PODC, 1995)

On the Sparse Set Conjecture for Sets with Low Denisty. - Harry Buhrman; Montserrat Hermo (STACS, 1995)

SPARSE Reduces Conjunctively to TALLY. - Harry Buhrman; Edith Hemaspaandra; Luc Longpré (SIAM J. Comput., 1995)

Optimal Routing Tables. - Harry Buhrman; Jaap-Henk Hoepman; Paul M. B. Vitányi (PODC, 1996)

The Complexity of Generating and Checking Proffs of Membership. - Harry Buhrman; Thomas Thierauf (STACS, 1996)

Random Strings Make Hard Instances. - Harry Buhrman; Pekka Orponen (J. Comput. Syst. Sci., 1996)

P-Selektive Self-Reducible Sets: A New Characterization of P. - Harry Buhrman; Leen Torenvliet (J. Comput. Syst. Sci., 1996)

A short note on Shor's factoring algorithm. - Harry Buhrman (SIGACT News, 1996)

Six Hypotheses in Search of a Theorem. - Harry Buhrman; Lance Fortnow; Leen Torenvliet (CCC, 1997)

Results on Resource-Bounded Measure. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow (ICALP, 1997)

Kolmogorov random graphs. - Harry Buhrman; Ming Li 001; Paul M. B. Vitányi (SEQUENCES, 1997)

Resource-Bounded Kolmogorov Complexity Revisited. - Harry Buhrman; Lance Fortnow (STACS, 1997)

An Excursion to the Kolmogorov Random Strings. - Harry Buhrman; Elvira Mayordomo (J. Comput. Syst. Sci., 1997)

Nonrelativizing Separations. - Harry Buhrman; Lance Fortnow; Thomas Thierauf (CCC, 1998)

Mutual Search (Extended Abstract). - Harry Buhrman; Matthew K. Franklin; Juan A. Garay; Jaap-Henk Hoepman; John Tromp; Paul M. B. Vitányi (SODA, 1998)

A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). - Harry Buhrman; Dieter van Melkebeek; Kenneth W. Regan; D. Sivakumar; Martin Strauss 001 (STACS, 1998)

NP Might Not Be As Easy As Detecting Unique Solutions. - Richard Beigel; Harry Buhrman; Lance Fortnow (STOC, 1998)

Quantum vs. Classical Communication and Computation. - Harry Buhrman; Richard Cleve; Avi Wigderson (STOC, 1998)

Lower Bounds for Quantum Search and Derandomization - Harry Buhrman; Ronald de Wolf (CoRR, 1998)

Functions Computable with Nonadaptive Queries to NP. - Harry Buhrman; Jim Kadin; Thomas Thierauf (Theory Comput. Syst., 1998)

Splittings, Robustness, and Structure of Complete Sets. - Harry Buhrman; Albrecht Hoene; Leen Torenvliet (SIAM J. Comput., 1998)

Quantum Bounded Query Complexity. - Harry Buhrman; Wim van Dam (CCC, 1999)

Complicated Complementations. - Harry Buhrman; Leen Torenvliet (CCC, 1999)

Bounds for Small-Error and Zero-Error Quantum Algorithms. - Harry Buhrman; Richard Cleve; Ronald de Wolf; Christof Zalka (FOCS, 1999)

New Applications of the Incompressibility Method. - Harry Buhrman; Tao Jiang 001; Ming Li 001; Paul M. B. Vitányi (ICALP, 1999)

One-sided Versus Two-sided Error in Probabilistic Computation. - Harry Buhrman; Lance Fortnow (STACS, 1999)

A Lower Bound for Quantum Search of an Ordered List. - Harry Buhrman; Ronald de Wolf (Inf. Process. Lett., 1999)

Mutual Search. - Harry Buhrman; Matthew K. Franklin; Juan A. Garay; Jaap-Henk Hoepman; John Tromp; Paul M. B. Vitányi (J. ACM, 1999)

Two Queries. - Harry Buhrman; Lance Fortnow (J. Comput. Syst. Sci., 1999)

Hard Sets Are Hard to Find. - Harry Buhrman; Dieter van Melkebeek (J. Comput. Syst. Sci., 1999)

Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method. - Harry Buhrman; Jaap-Henk Hoepman; Paul M. B. Vitányi (SIAM J. Comput., 1999)

Kolmogorov Random Graphs and the Incompressibility Method. - Harry Buhrman; Ming Li 001; John Tromp; Paul M. B. Vitányi (SIAM J. Comput., 1999)

New Bounds for the Language Compression Problem. - Harry Buhrman; Sophie Laplante; Peter Bro Miltersen (CCC, 2000)

Optimal Proof Systems and Sparse Sets. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow; Dieter van Melkebeek (STACS, 2000)

Quantum Computing and Communication Complexity. - Harry Buhrman (Bull. EATCS, 2000)

Quantum Entanglement and Communication Complexity. - Harry Buhrman; Richard Cleve; Wim van Dam (SIAM J. Comput., 2000)

Separating Complexity Classes Using Autoreducibility. - Harry Buhrman; Lance Fortnow; Dieter van Melkebeek; Leen Torenvliet (SIAM J. Comput., 2000)

A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. - Harry Buhrman; Dieter van Melkebeek; Kenneth W. Regan; D. Sivakumar; Martin Strauss 001 (SIAM J. Comput., 2000)

Randomness is Hard. - Harry Buhrman; Leen Torenvliet (SIAM J. Comput., 2000)

New applications of the incompressibility method: Part II. - Harry Buhrman; Tao Jiang 001; Ming Li 001; Paul M. B. Vitányi (Theor. Comput. Sci., 2000)

Quantum Computing and Communication Complexity. - Harry Buhrman (Current Trends in Theoretical Computer Science, 2001)

Communication Complexity Lower Bounds by Polynomials. - Harry Buhrman; Ronald de Wolf (CCC, 2001)

Time and Space Bounds for Reversible Simulation. - Harry Buhrman; John Tromp; Paul M. B. Vitányi (ICALP, 2001)

Two oracles that force a big crunch. - Harry Buhrman; Stephen A. Fenner; Lance Fortnow; Leen Torenvliet (Comput. Complex., 2001)

Quantum lower bounds by polynomials. - Robert Beals; Harry Buhrman; Richard Cleve; Michele Mosca; Ronald de Wolf (J. ACM, 2001)

The Communication Complexity of Enumeration, Elimination, and Selection. - Andris Ambainis; Harry Buhrman; William I. Gasarch; Bala Kalyanasundaram; Leen Torenvliet (J. Comput. Syst. Sci., 2001)

Resource-Bounded Kolmogorov Complexity Revisited. - Harry Buhrman; Lance Fortnow; Sophie Laplante (SIAM J. Comput., 2001)

Compressibility and Resource Bounded Measure. - Harry Buhrman; Luc Longpré (SIAM J. Comput., 2001)

Are Bitvectors Optimal? - Harry Buhrman; Peter Bro Miltersen; Jaikumar Radhakrishnan; Srinivasan Venkatesh 001 (SIAM J. Comput., 2002)

Complexity measures and decision tree complexity: a survey. - Harry Buhrman; Ronald de Wolf (Theor. Comput. Sci., 2002)

Distributed Quantum Computing. - Harry Buhrman; Hein Röhrig (MFCS, 2003)

One Bit of Advice. - Harry Buhrman; Richard Chang 001; Lance Fortnow (STACS, 2003)

Robust Quantum Algorithms and Polynomials - Harry Buhrman; Ilan Newman; Hein Röhrig; Ronald de Wolf (CoRR, 2003)

Quantum zero-error algorithms cannot be composed. - Harry Buhrman; Ronald de Wolf (Inf. Process. Lett., 2003)

Multiparty Quantum Coin Flipping. - Andris Ambainis; Harry Buhrman; Yevgeniy Dodis; Hein Röhrig (CCC, 2004)

Separating Complexity Classes Using Structural Properties. - Harry Buhrman; Leen Torenvliet (CCC, 2004)

04421 Abstracts Collection - Algebraic Methods in Computational Complexity. - Harry Buhrman; Lance Fortnow; Thomas Thierauf (Algebraic Methods in Computational Complexity, 2004)

What Can be Efficiently Reduced to the K-Random Strings? - Eric Allender; Harry Buhrman; Michal Koucký 001 (STACS, 2004)

Individual Communication Complexity: Extended Abstract. - Harry Buhrman; Hartmut Klauck; Nikolai K. Vereshchagin; Paul M. B. Vitányi (STACS, 2004)

What Can be Efficiently Reduced to the Kolmogorov-Random Strings? - Eric Allender; Harry Buhrman; Michal Koucký 001 (Electron. Colloquium Comput. Complex., 2004)

Increasing Kolmogorov Complexity - Harry Buhrman; Lance Fortnow; Ilan Newman; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2004)

Quantum Computing. - Harry Buhrman (CiE, 2005)

Language compression and pseudorandom generators. - Harry Buhrman; Troy Lee; Dieter van Melkebeek (Comput. Complex., 2005)

A Post's Program for Complexity Theory. - Harry Buhrman; Leen Torenvliet (Bull. EATCS, 2005)

Some Results on Derandomization. - Harry Buhrman; Lance Fortnow; Aduri Pavan (Theory Comput. Syst., 2005)

Quantum Algorithms for Element Distinctness. - Harry Buhrman; Christoph Dürr; Mark Heiligman; Peter Høyer; Frédéric Magniez; Miklos Santha; Ronald de Wolf (SIAM J. Comput., 2005)

New Limits on Fault-Tolerant Quantum Computation. - Harry Buhrman; Richard Cleve; Monique Laurent; Noah Linden; Alexander Schrijver; Falk Unger (FOCS, 2006)

Quantum verification of matrix products. - Harry Buhrman; Robert Spalek (SODA, 2006)

Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. - Harry Buhrman; Leen Torenvliet; Falk Unger (STACS, 2006)

On the importance of having an identity or, is consensus really universal?. - Harry Buhrman; Alessandro Panconesi; Riccardo Silvestri; Paul M. B. Vitányi (Distributed Comput., 2006)

Inverting onto functions might not be hard. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2006)

Enumerations of the Kolmogorov function. - Richard Beigel; Harry Buhrman; Peter A. Fejer; Lance Fortnow; Piotr Grabowski; Luc Longpré; Andrej Muchnik; Frank Stephan 001; Leen Torenvliet (J. Symb. Log., 2006)

Power from Random Strings. - Eric Allender; Harry Buhrman; Michal Koucký 001; Dieter van Melkebeek; Detlef Ronneburger (SIAM J. Comput., 2006)

On Computation and Communication with Small Bias. - Harry Buhrman; Nikolai K. Vereshchagin; Ronald de Wolf (CCC, 2007)

Inverting Onto Functions and Polynomial Hierarchy. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (CSR, 2007)

07411 Executive Summary – Algebraic Methods in Computational Complexity. - Manindra Agrawal; Harry Buhrman; Lance Fortnow; Thomas Thierauf (Algebraic Methods in Computational Complexity, 2007)

07411 Abstracts Collection – Algebraic Methods in Computational Complexity. - Manindra Agrawal; Harry Buhrman; Lance Fortnow; Thomas Thierauf (Algebraic Methods in Computational Complexity, 2007)

On Computation and Communication with Small Bias. - Harry Buhrman (SAGA, 2007)

Quantum Information Processing. - Bram Vermeer; Harry Buhrman (ERCIM News, 2007)

Individual communication complexity. - Harry Buhrman; Hartmut Klauck; Nikolai K. Vereshchagin; Paul M. B. Vitányi (J. Comput. Syst. Sci., 2007)

Robust Polynomials and Quantum Algorithms. - Harry Buhrman; Ilan Newman; Hein Röhrig; Ronald de Wolf (Theory Comput. Syst., 2007)

NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. - Harry Buhrman; John M. Hitchcock (CCC, 2008)

Randomised Individual Communication Complexity. - Harry Buhrman; Michal Koucký 001; Nikolai K. Vereshchagin (CCC, 2008)

NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. - Harry Buhrman; John M. Hitchcock (Electron. Colloquium Comput. Complex., 2008)

Foreword. - Harry Buhrman (J. Comput. Syst. Sci., 2008)

Quantum Property Testing. - Harry Buhrman; Lance Fortnow; Ilan Newman; Hein Röhrig (SIAM J. Comput., 2008)

Unconditional Lower Bounds against Advice. - Harry Buhrman; Lance Fortnow; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2009)

Derandomizing from Random Strings. - Harry Buhrman; Lance Fortnow; Michal Koucký 001; Bruno Loff (CCC, 2010)

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. - Scott Aaronson; Baris Aydinlioglu; Harry Buhrman; John M. Hitchcock; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2010)

Sparse Selfreducible Sets and Nonuniform Lower Bounds. - Harry Buhrman; Leen Torenvliet; Falk Unger; Nikolai K. Vereshchagin (Electron. Colloquium Comput. Complex., 2010)

Learning parities in the mistake-bound model. - Harry Buhrman; David García-Soriano; Arie Matsliah (Inf. Process. Lett., 2010)

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? - Harry Buhrman; Lance Fortnow; Michal Koucký 001; John D. Rogers; Nikolai K. Vereshchagin (Theory Comput. Syst., 2010)

Non-Uniform Reductions. - Harry Buhrman; Benjamin J. Hescott; Steven Homer; Leen Torenvliet (Theory Comput. Syst., 2010)

The Garden-Hose Game: A New Model of Computation, and Application to Position-Based Quantum Cryptography - Harry Buhrman; Serge Fehr; Christian Schaffner; Florian Speelman (CoRR, 2011)

Position-Based Quantum Cryptography. - Harry Buhrman; Serge Fehr; Christian Schaffner (ERCIM News, 2011)

Some Mathematical Refinements Concerning Error Minimization in the Genetic Code. - Harry Buhrman; Peter T. S. van der Gulik; Steven Kelk; Wouter M. Koolen; Leen Stougie (IEEE ACM Trans. Comput. Biol. Bioinform., 2011)

Complete Insecurity of Quantum Protocols for Classical Two-Party Computation - Harry Buhrman; Matthias Christandl; Christian Schaffner (CoRR, 2012)

Violating the Shannon capacity of metric graphs with entanglement - Jop Briët; Harry Buhrman; Dion Gijswijt (CoRR, 2012)

Reductions to the set of random strings: the resource-bounded case. - Eric Allender; Harry Buhrman; Luke Friedman; Bruno Loff (Electron. Colloquium Comput. Complex., 2012)

Towards a Reverse Newman's Theorem in Interactive Information Complexity. - Joshua Brody; Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman (Electron. Colloquium Comput. Complex., 2012)

Near-Optimal and Explicit Bell Inequality Violations. - Harry Buhrman; Oded Regev 001; Giannicola Scarpa; Ronald de Wolf (Theory Comput., 2012)

The garden-hose model. - Harry Buhrman; Serge Fehr; Christian Schaffner; Florian Speelman (ITCS, 2013)

Learning Reductions to Sparse Sets. - Harry Buhrman; Lance Fortnow; John M. Hitchcock; Bruno Loff (MFCS, 2013)

The non-adaptive query complexity of testing k-parities. - Harry Buhrman; David García-Soriano; Arie Matsliah; Ronald de Wolf (Chic. J. Theor. Comput. Sci., 2013)

Multipartite entanglement in XOR games. - Jop Briët; Harry Buhrman; Troy Lee; Thomas Vidick (Quantum Inf. Comput., 2013)

Turing in Quantumland. - Harry Buhrman (Turing's Legacy, 2014)

On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. - Harry Buhrman; Serge Fehr; Christian Schaffner (TQC, 2014)

Computing with a full memory: Catalytic space. - Harry Buhrman; Richard Cleve; Michal Koucký 001; Bruno Loff; Florian Speelman (Electron. Colloquium Comput. Complex., 2014)

Position-Based Quantum Cryptography: Impossibility and Constructions. - Harry Buhrman; Nishanth Chandran; Serge Fehr; Ran Gelles; Vipul Goyal; Rafail Ostrovsky; Christian Schaffner (SIAM J. Comput., 2014)

Round Elimination in Exact Communication Complexity. - Jop Briët; Harry Buhrman; Debbie W. Leung; Teresa Piovesan; Florian Speelman (TQC, 2015)

Hardness of Approximation for Knapsack Problems. - Harry Buhrman; Bruno Loff; Leen Torenvliet (Theory Comput. Syst., 2015)

Entanglement-Assisted Zero-Error Source-Channel Coding. - Jop Briët; Harry Buhrman; Monique Laurent; Teresa Piovesan; Giannicola Scarpa (IEEE Trans. Inf. Theory, 2015)

Towards a Reverse Newman's Theorem in Interactive Information Complexity. - Joshua Brody; Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman; Nikolai K. Vereshchagin (Algorithmica, 2016)

Distinguishing Two Probability Ensembles with One Sample from each Ensemble. - Luis Filipe Coelho Antunes; Harry Buhrman; Armando Matos; André Souto; Andreia Teixeira (Theory Comput. Syst., 2016)

Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. - Harry Buhrman; Matthias Christandl; Jeroen Zuiddam (ITCS, 2017)

The Case for Quantum Software. - Harry Buhrman; Floor van de Pavert (ERCIM News, 2018)

Catalytic Space: Non-determinism and Hierarchy. - Harry Buhrman; Michal Koucký 001; Bruno Loff; Florian Speelman (Theory Comput. Syst., 2018)

Bounding Quantum-Classical Separations for Classes of Nonlocal Games. - Tom Bannink; Jop Briët; Harry Buhrman; Farrokh Labib; Troy Lee (STACS, 2019)

The Quantum Strong Exponential-Time Hypothesis. - Harry Buhrman; Subhasree Patro; Florian Speelman (CoRR, 2019)

A Framework of Quantum Strong Exponential-Time Hypotheses. - Harry Buhrman; Subhasree Patro; Florian Speelman (STACS, 2021)

High Entropy Random Selection Protocols. - Harry Buhrman; Matthias Christandl; Michal Koucký 001; Zvi Lotker; Boaz Patt-Shamir; Nikolai K. Vereshchagin (Algorithmica, 2021)

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. - Harry Buhrman; Bruno Loff; Subhasree Patro; Florian Speelman (ITCS, 2022)

Memory Compression with Quantum Random-Access Gates. - Harry Buhrman; Bruno Loff; Subhasree Patro; Florian Speelman (TQC, 2022)

Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. - Andris Ambainis; Harry Buhrman; Koen Leijnse; Subhasree Patro; Florian Speelman (CoRR, 2022)

Quantum Majority Vote. - Harry Buhrman; Noah Linden; Laura Mancinska; Ashley Montanaro; Maris Ozols (ITCS, 2023)

Noisy decoding by shallow circuits with parities: classical and quantum. - Jop Briët; Harry Buhrman; Davi Castro-Silva; Niels M. P. Neumann (CoRR, 2023)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. - Scott Aaronson; Harry Buhrman; William Kretschmer (Electron. Colloquium Comput. Complex., 2023)

Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). - Jop Briët; Harry Buhrman; Davi Castro-Silva; Niels M. P. Neumann (ITCS, 2024)

Beating Grover search for low-energy estimation and state preparation. - Harry Buhrman; Sevag Gharibian; Zeph Landau; François Le Gall; Norbert Schuch; Suguru Tamaki (CoRR, 2024)

Classical versus quantum queries in quantum PCPs with classical proofs. - Harry Buhrman; François Le Gall; Jordi Weggemans (CoRR, 2024)

Relating non-local quantum computation to information theoretic cryptography. - Rene Allerstorfer; Harry Buhrman; Alex May 003; Florian Speelman; Philip Verduyn Lunel (Quantum, 2024)

State preparation by shallow circuits using feed forward. - Harry Buhrman; Marten Folkertsma; Bruno Loff; Niels M. P. Neumann (Quantum, 2024)

Quantum Catalytic Space. - Harry Buhrman; Marten Folkertsma; Ian Mertz; Florian Speelman; Sergii Strelchuk; Sathyawageeswar Subramanian; Quinten Tupker (TQC, 2025)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians. - Harry Buhrman; Jonas Helsen; Jordi Weggemans (Quantum, 2025)