Harry Buhrman

Publication Activity (10 Years)

Years Active: 1991-2024
Publications (10 Years): 26

Top Venues

CoRR

ITCS

Theory Comput. Syst.

TQC

Publications

Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). ITCS (2024)
Harry Buhrman, Jonas Helsen, Jordi Weggemans
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians. CoRR (2024)
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
Beating Grover search for low-energy estimation and state preparation. CoRR (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR (2023)
Harry Buhrman, Noah Linden, Laura Mancinska, Ashley Montanaro, Maris Ozols
Quantum Majority Vote. ITCS (2023)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. (2023)
Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann
Noisy decoding by shallow circuits with parities: classical and quantum. CoRR (2023)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Memory Compression with Quantum Random-Access Gates. CoRR (2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. ITCS (2022)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Memory Compression with Quantum Random-Access Gates. TQC (2022)
Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. CoRR (2022)
Harry Buhrman, Subhasree Patro, Florian Speelman
A Framework of Quantum Strong Exponential-Time Hypotheses. STACS (2021)
Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
High Entropy Random Selection Protocols. Algorithmica 83 (2) (2021)
Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks. CoRR (2021)
Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica 81 (1) (2019)
Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee
Bounding Quantum-Classical Separations for Classes of Nonlocal Games. STACS (2019)
Harry Buhrman, Subhasree Patro, Florian Speelman
The Quantum Strong Exponential-Time Hypothesis. CoRR (2019)
Harry Buhrman, Floor van de Pavert
The Case for Quantum Software. ERCIM News 2018 (112) (2018)
Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman
Round elimination in exact communication complexity. CoRR (2018)
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62 (1) (2018)
Harry Buhrman, Matthias Christandl, Jeroen Zuiddam
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. ITCS (2017)
Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Catalytic Space: Non-determinism and Hierarchy. STACS (2016)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica 76 (3) (2016)
Luis Filipe Coelho Antunes, Harry Buhrman, Armando Matos, André Souto, Andreia Teixeira
Distinguishing Two Probability Ensembles with One Sample from each Ensemble. Theory Comput. Syst. 59 (3) (2016)
Harry Buhrman, Matthias Christandl, Jeroen Zuiddam
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. CoRR (2016)
Harry Buhrman, Bruno Loff, Leen Torenvliet
Hardness of Approximation for Knapsack Problems. Theory Comput. Syst. 56 (2) (2015)
Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan, Giannicola Scarpa
Entanglement-Assisted Zero-Error Source-Channel Coding. IEEE Trans. Inf. Theory 61 (2) (2015)
Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman
Round Elimination in Exact Communication Complexity. TQC (2015)
Harry Buhrman, Serge Fehr, Christian Schaffner
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. TQC (2014)
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Position-Based Quantum Cryptography: Impossibility and Constructions. SIAM J. Comput. 43 (1) (2014)
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the set of random strings: The resource-bounded case. Log. Methods Comput. Sci. 10 (3) (2014)
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman
Computing with a full memory: catalytic space. STOC (2014)
Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf
The non-adaptive query complexity of testing k-parities. Chic. J. Theor. Comput. Sci. 2013 (2013)
Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff
Learning Reductions to Sparse Sets. MFCS (2013)
Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick
Multipartite entanglement in XOR games. Quantum Inf. Comput. 13 (3-4) (2013)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Computational Complexity Conference (2013)
Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman
The garden-hose model. ITCS (2013)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS (2012)
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Reductions to the set of random strings: the resource-bounded case. Electron. Colloquium Comput. Complex. 19 (2012)
Harry Buhrman, Matthias Christandl, Christian Schaffner
Complete Insecurity of Quantum Protocols for Classical Two-Party Computation CoRR (2012)
Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf
The non-adaptive query complexity of testing k-parities CoRR (2012)
Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
Near-Optimal and Explicit Bell Inequality Violations. Theory Comput. 8 (1) (2012)
Jop Briët, Harry Buhrman, Dion Gijswijt
Violating the Shannon capacity of metric graphs with entanglement CoRR (2012)
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electron. Colloquium Comput. Complex. 19 (2012)
Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
Near-Optimal and Explicit Bell Inequality Violations. Computational Complexity Conference (2011)
Harry Buhrman, Serge Fehr, Christian Schaffner
Position-Based Quantum Cryptography. ERCIM News 2011 (85) (2011)
Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman
The Garden-Hose Game: A New Model of Computation, and Application to Position-Based Quantum Cryptography CoRR (2011)
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Position-Based Quantum Cryptography: Impossibility and Constructions. CRYPTO (2011)
Harry Buhrman, Peter T. S. van der Gulik, Steven Kelk, Wouter M. Koolen, Leen Stougie
Some Mathematical Refinements Concerning Error Minimization in the Genetic Code. IEEE ACM Trans. Comput. Biol. Bioinform. 8 (5) (2011)
Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. 17 (2010)
Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet
Non-Uniform Reductions. Theory Comput. Syst. 47 (2) (2010)
Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electron. Colloquium Comput. Complex. 17 (2010)
Harry Buhrman, David García-Soriano, Arie Matsliah
Learning parities in the mistake-bound model. Inf. Process. Lett. 111 (1) (2010)
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Position-Based Quantum Cryptography: Impossibility and Constructions. IACR Cryptol. ePrint Arch. 2010 (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46 (1) (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings. Computational Complexity Conference (2010)
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Position-Based Quantum Cryptography: Impossibility and Constructions CoRR (2010)
Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff
Derandomizing from Random Strings CoRR (2009)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity (2009)
Harry Buhrman, David García-Soriano, Arie Matsliah
Learning parities in the mistake-bound model. Electron. Colloquium Comput. Complex. 16 (2009)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. 16 (2009)
Harry Buhrman, David García-Soriano, Arie Matsliah
Learning Parities in the Mistake-Bound model. Algebraic Methods in Computational Complexity (2009)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
Unconditional Lower Bounds against Advice. ICALP (1) (2009)
Harry Buhrman, John M. Hitchcock
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. Computational Complexity Conference (2008)
Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin
Randomised Individual Communication Complexity. Computational Complexity Conference (2008)
Harry Buhrman, John M. Hitchcock
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electron. Colloquium Comput. Complex. 15 (022) (2008)
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig
Quantum Property Testing. SIAM J. Comput. 37 (5) (2008)
Harry Buhrman
Foreword. J. Comput. Syst. Sci. 74 (3) (2008)
Harry Buhrman
On Computation and Communication with Small Bias. SAGA (2007)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Inverting Onto Functions and Polynomial Hierarchy. CSR (2007)
Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2007)
Nikolai K. Vereshchagin, Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir
High Entropy Random Selection Protocols. Algebraic Methods in Computational Complexity (2007)
Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity (2007)
Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf
On Computation and Communication with Small Bias. Computational Complexity Conference (2007)
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
Individual communication complexity. J. Comput. Syst. Sci. 73 (6) (2007)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40 (4) (2007)
Bram Vermeer, Harry Buhrman
Quantum Information Processing. ERCIM News 2007 (71) (2007)
Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin
High Entropy Random Selection Protocols. APPROX-RANDOM (2007)
Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi
On the importance of having an identity or, is consensus really universal?. Distributed Comput. 18 (3) (2006)
Harry Buhrman, Robert Spalek
Quantum verification of matrix products. SODA (2006)
Eric Allender, Harry Buhrman, Michal Koucký
What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Log. 138 (1-3) (2006)
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger
Power from Random Strings. SIAM J. Comput. 35 (6) (2006)
Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet
Enumerations of the Kolmogorov function. J. Symb. Log. 71 (2) (2006)
Harry Buhrman, Leen Torenvliet, Falk Unger
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. STACS (2006)
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. 13 (024) (2006)
Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger
New Limits on Fault-Tolerant Quantum Computation. FOCS (2006)
Harry Buhrman, Leen Torenvliet
A Post's Program for Complexity Theory. Bull. EATCS 85 (2005)
Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf
Quantum Algorithms for Element Distinctness. SIAM J. Comput. 34 (6) (2005)
Harry Buhrman, Lance Fortnow, Aduri Pavan
Some Results on Derandomization. Theory Comput. Syst. 38 (2) (2005)
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf
Robust Polynomials and Quantum Algorithms. STACS (2005)
Harry Buhrman, Troy Lee, Dieter van Melkebeek
Language compression and pseudorandom generators. Comput. Complex. 14 (3) (2005)
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
Increasing Kolmogorov Complexity. STACS (2005)
Harry Buhrman
Quantum Computing. CiE (2005)
Troy Lee, Dieter van Melkebeek, Harry Buhrman
Language Compression and Pseudorandom Generators Electron. Colloquium Comput. Complex. (002) (2004)
Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi
Individual Communication Complexity: Extended Abstract. STACS (2004)
Eric Allender, Harry Buhrman, Michal Koucký
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electron. Colloquium Comput. Complex. (044) (2004)
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin
Increasing Kolmogorov Complexity Electron. Colloquium Comput. Complex. (081) (2004)
Eric Allender, Harry Buhrman, Michal Koucký
What Can be Efficiently Reduced to the K-Random Strings? STACS (2004)

Harry Buhrman.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Harry Buhrman