Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDHarry Buhrman
Person information
- affiliation: National Research Institute for Mathematics and Computer Science, Amsterdam, Netherlands
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2021
[j58]Harry Buhrman, Matthias Christandl, Michal Koucký
, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. Algorithmica 83(2): 667-694 (2021)- 2019
- [j57]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica 81(1): 179-200 (2019) - 2018
- [j56]Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62(1): 116-135 (2018) - 2016
- [j55]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): 749-781 (2016) - [j54]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): 517-531 (2016) - 2015
- [j53]Harry Buhrman, Bruno Loff, Leen Torenvliet:
Hardness of Approximation for Knapsack Problems. Theory Comput. Syst. 56(2): 372-393 (2015) - [j52]Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan, Giannicola Scarpa:
Entanglement-Assisted Zero-Error Source-Channel Coding. IEEE Trans. Inf. Theory 61(2): 1124-1138 (2015) - 2014
- [j51]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) - [j50]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): 150-178 (2014) - 2013
- [j49]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) - [j48]Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick:
Multipartite entanglement in XOR games. Quantum Inf. Comput. 13(3-4): 334-360 (2013) - 2012
- [j47]Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf:
Near-Optimal and Explicit Bell Inequality Violations. Theory Comput. 8(1): 623-645 (2012) - 2011
- [j46]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): 1358-1372 (2011) - 2010
- [j45]Harry Buhrman, David García-Soriano, Arie Matsliah:
Learning parities in the mistake-bound model. Inf. Process. Lett. 111(1): 16-21 (2010) - [j44]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): 143-156 (2010) - [j43]Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet:
Non-Uniform Reductions. Theory Comput. Syst. 47(2): 317-341 (2010) - 2008
- [j42]Harry Buhrman:
Foreword. J. Comput. Syst. Sci. 74(3): 297 (2008) - [j41]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008) - 2007
- [j40]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual communication complexity. J. Comput. Syst. Sci. 73(6): 973-985 (2007) - [j39]Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379-395 (2007) - 2006
- [j38]Eric Allender, Harry Buhrman, Michal Koucký:
What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Log. 138(1-3): 2-19 (2006) - [j37]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): 167-176 (2006) - [j36]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): 501-528 (2006) - [j35]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings. SIAM J. Comput. 35(6): 1467-1493 (2006) - 2005
- [j34]Harry Buhrman, Troy Lee, Dieter van Melkebeek:
Language compression and pseudorandom generators. Comput. Complex. 14(3): 228-255 (2005) - [j33]Harry Buhrman, Leen Torenvliet:
A Post's Program for Complexity Theory. Bull. EATCS 85: 41-51 (2005) - [j32]Harry Buhrman, Lance Fortnow, Aduri Pavan:
Some Results on Derandomization. Theory Comput. Syst. 38(2): 211-227 (2005) - [j31]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): 1324-1330 (2005) - 2003
- [j30]Harry Buhrman, Ronald de Wolf:
Quantum zero-error algorithms cannot be composed. Inf. Process. Lett. 87(2): 79-84 (2003) - 2002
- [j29]Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
Are Bitvectors Optimal? SIAM J. Comput. 31(6): 1723-1744 (2002) - [j28]Harry Buhrman, Ronald de Wolf:
Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1): 21-43 (2002) - 2001
- [j27]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet:
Two oracles that force a big crunch. Comput. Complex. 10(2): 93-116 (2001) - [j26]Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf:
Quantum lower bounds by polynomials. J. ACM 48(4): 778-797 (2001) - [j25]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. J. Comput. Syst. Sci. 63(2): 148-185 (2001) - [j24]Harry Buhrman, Luc Longpré:
Compressibility and Resource Bounded Measure. SIAM J. Comput. 31(3): 876-886 (2001) - [j23]Harry Buhrman, Lance Fortnow, Sophie Laplante:
Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. 31(3): 887-905 (2001) - 2000
- [j22]Harry Buhrman:
Quantum Computing and Communication Complexity. Bull. EATCS 70: 131-141 (2000) - [j21]Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet:
Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (2000) - [j20]Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss:
A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. SIAM J. Comput. 30(2): 576-601 (2000) - [j19]Harry Buhrman, Leen Torenvliet:
Randomness is Hard. SIAM J. Comput. 30(5): 1485-1501 (2000) - [j18]Harry Buhrman, Richard Cleve, Wim van Dam:
Quantum Entanglement and Communication Complexity. SIAM J. Comput. 30(6): 1829-1841 (2000) - [j17]Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi:
New applications of the incompressibility method: Part II. Theor. Comput. Sci. 235(1): 59-70 (2000) - 1999
- [j16]Harry Buhrman, Ronald de Wolf:
A Lower Bound for Quantum Search of an Ordered List. Inf. Process. Lett. 70(5): 205-209 (1999) - [j15]Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi:
Mutual Search. J. ACM 46(4): 517-536 (1999) - [j14]Harry Buhrman, Lance Fortnow:
Two Queries. J. Comput. Syst. Sci. 59(2): 182-194 (1999) - [j13]Harry Buhrman, Dieter van Melkebeek:
Hard Sets Are Hard to Find. J. Comput. Syst. Sci. 59(2): 327-345 (1999) - [j12]Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi:
Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method. SIAM J. Comput. 28(4): 1414-1432 (1999) - [j11]Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi:
Kolmogorov Random Graphs and the Incompressibility Method. SIAM J. Comput. 29(2): 590-599 (1999) - 1998
- [j10]Harry Buhrman, Jim Kadin, Thomas Thierauf:
Functions Computable with Nonadaptive Queries to NP. Theory Comput. Syst. 31(1): 77-92 (1998) - [j9]Harry Buhrman, Albrecht Hoene, Leen Torenvliet:
Splittings, Robustness, and Structure of Complete Sets. SIAM J. Comput. 27(3): 637-653 (1998) - 1997
- [j8]Harry Buhrman, Elvira Mayordomo:
An Excursion to the Kolmogorov Random Strings. J. Comput. Syst. Sci. 54(3): 393-399 (1997) - 1996
- [j7]Harry Buhrman, Leen Torenvliet:
P-Selektive Self-Reducible Sets: A New Characterization of P. J. Comput. Syst. Sci. 53(2): 210-217 (1996) - [j6]Harry Buhrman, Pekka Orponen:
Random Strings Make Hard Instances. J. Comput. Syst. Sci. 53(2): 261-266 (1996) - [j5]Harry Buhrman:
A short note on Shor's factoring algorithm. SIGACT News 27(1): 89-90 (1996) - 1995
- [j4]Harry Buhrman, Edith Hemaspaandra, Luc Longpré:
SPARSE Reduces Conjunctively to TALLY. SIAM J. Comput. 24(4): 673-681 (1995) - 1993
- [j3]Harry Buhrman, Edith Spaan, Leen Torenvliet:
The Relative Power of Logspace and Polynomial Time Reductions. Comput. Complex. 3: 231-244 (1993) - [j2]Harry Buhrman, Leen Torenvliet, Peter van Emde Boas:
Twenty Questions to a P-Selector. Inf. Process. Lett. 48(4): 201-204 (1993) - 1991
- [j1]Harry Buhrman, Steven Homer, Leen Torenvliet:
Completeness for Nondeterministic Complexity Classes. Math. Syst. Theory 24(3): 179-200 (1991)
Conference and Workshop Papers
- 2024
- [c87]Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS 2024: 1:1-1:24 - [c86]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: 21:1-21:11 - 2023
- [c85]Harry Buhrman, Noah Linden, Laura Mancinska, Ashley Montanaro, Maris Ozols:
Quantum Majority Vote. ITCS 2023: 29:1-29:1 - 2022
- [c84]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: 31:1-31:12 - [c83]Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman:
Memory Compression with Quantum Random-Access Gates. TQC 2022: 10:1-10:19 - 2021
- [c82]Harry Buhrman, Subhasree Patro, Florian Speelman:
A Framework of Quantum Strong Exponential-Time Hypotheses. STACS 2021: 19:1-19:19 - 2019
- [c81]Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee:
Bounding Quantum-Classical Separations for Classes of Nonlocal Games. STACS 2019: 12:1-12:11 - 2017
- [c80]Harry Buhrman, Matthias Christandl, Jeroen Zuiddam:
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. ITCS 2017: 24:1-24:18 - 2016
- [c79]Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Catalytic Space: Non-determinism and Hierarchy. STACS 2016: 24:1-24:13 - 2015
- [c78]Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman:
Round Elimination in Exact Communication Complexity. TQC 2015: 206-225 - 2014
- [c77]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: catalytic space. STOC 2014: 857-866 - [c76]Harry Buhrman, Serge Fehr, Christian Schaffner:
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. TQC 2014: 24-35 - 2013
- [c75]Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. CCC 2013: 24-33 - [c74]Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman:
The garden-hose model. ITCS 2013: 145-158 - [c73]Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff:
Learning Reductions to Sparse Sets. MFCS 2013: 243-253 - 2012
- [c72]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS 2012: 88-99 - 2011
- [c71]Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf:
Near-Optimal and Explicit Bell Inequality Violations. CCC 2011: 157-166 - [c70]Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner:
Position-Based Quantum Cryptography: Impossibility and Constructions. CRYPTO 2011: 429-446 - 2010
- [c69]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CCC 2010: 58-63 - 2009
- [c68]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209 - 2008
- [c67]Harry Buhrman, John M. Hitchcock:
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. CCC 2008: 1-7 - [c66]Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin:
Randomised Individual Communication Complexity. CCC 2008: 321-331 - 2007
- [c65]Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379 - [c64]Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf:
On Computation and Communication with Small Bias. CCC 2007: 24-32 - [c63]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103 - [c62]Harry Buhrman:
On Computation and Communication with Small Bias. SAGA 2007: 1 - 2006
- [c61]Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger:
New Limits on Fault-Tolerant Quantum Computation. FOCS 2006: 411-419 - [c60]Harry Buhrman, Robert Spalek:
Quantum verification of matrix products. SODA 2006: 880-889 - [c59]Harry Buhrman, Leen Torenvliet, Falk Unger:
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. STACS 2006: 455-468 - 2005
- [c58]Harry Buhrman:
Quantum Computing. CiE 2005: 68-68 - [c57]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. STACS 2005: 412-421 - [c56]Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Polynomials and Quantum Algorithms. STACS 2005: 593-604 - 2004
- [c55]Harry Buhrman, Troy Lee, Dieter van Melkebeek:
Language Compression and Pseudorandom Generators. CCC 2004: 15-28 - [c54]Harry Buhrman, Leen Torenvliet:
Separating Complexity Classes Using Structural Properties. CCC 2004: 130-138 - [c53]Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig:
Multiparty Quantum Coin Flipping. CCC 2004: 250-259 - [c52]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30 - [c51]Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the K-Random Strings? STACS 2004: 584-595 - 2003
- [c50]Harry Buhrman, Hein Röhrig:
Distributed Quantum Computing. MFCS 2003: 1-20 - [c49]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum property testing. SODA 2003: 480-488 - [c48]Harry Buhrman, Lance Fortnow, Aduri Pavan:
Some Results on Derandomization. STACS 2003: 212-222 - [c47]Harry Buhrman, Richard Chang, Lance Fortnow:
One Bit of Advice. STACS 2003: 547-558 - 2002
- [c46]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings. FOCS 2002: 669-678 - 2001
- [c45]Harry Buhrman, Ronald de Wolf:
Communication Complexity Lower Bounds by Polynomials. CCC 2001: 120-130 - [c44]Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf:
Quantum Algorithms for Element Distinctness. CCC 2001: 131-137 - [c43]Harry Buhrman, John Tromp, Paul M. B. Vitányi:
Time and Space Bounds for Reversible Simulation. ICALP 2001: 1017-1027 - 2000
- [c42]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. CCC 2000: 44-53 - [c41]Harry Buhrman, Sophie Laplante, Peter Bro Miltersen:
New Bounds for the Language Compression Problem. CCC 2000: 126-130 - [c40]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek:
Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418 - [c39]Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
Are bitvectors optimal? STOC 2000: 449-458 - [c38]Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi:
On the Importance of Having an Identity or is Consensus Really Universal? DISC 2000: 134-148 - 1999
- [c37]Harry Buhrman, Wim van Dam:
Quantum Bounded Query Complexity. CCC 1999: 149- - [c36]Harry Buhrman, Leen Torenvliet:
Complicated Complementations. CCC 1999: 227-236 - [c35]Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka:
Bounds for Small-Error and Zero-Error Quantum Algorithms. FOCS 1999: 358-368 - [c34]Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi:
New Applications of the Incompressibility Method. ICALP 1999: 220-229 - [c33]Harry Buhrman, Lance Fortnow:
One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109 - 1998
- [c32]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Nonrelativizing Separations. CCC 1998: 8-12 - [c31]Harry Buhrman, Lance Fortnow:
Two Queries. CCC 1998: 13- - [c30]Harry Buhrman, Dieter van Melkebeek:
Hard Sets are Hard to Find. CCC 1998: 170-181 - [c29]Harry Buhrman, Leen Torenvliet:
Randomness is Hard. CCC 1998: 249-260 - [c28]Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf:
Quantum Lower Bounds by Polynomials. FOCS 1998: 352-361 - [c27]Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi:
Mutual Search (Extended Abstract). SODA 1998: 481-489 - [c26]Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss:
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). STACS 1998: 161-171 - [c25]Harry Buhrman, Richard Cleve, Avi Wigderson:
Quantum vs. Classical Communication and Computation. STOC 1998: 63-68 - [c24]Richard Beigel, Harry Buhrman, Lance Fortnow:
NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208 - 1997
- [c23]Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Six Hypotheses in Search of a Theorem. CCC 1997: 2-12 - [c22]Harry Buhrman, Stephen A. Fenner, Lance Fortnow:
Results on Resource-Bounded Measure. ICALP 1997: 188-194 - [c21]Harry Buhrman, Ming Li, Paul M. B. Vitányi:
Kolmogorov random graphs. SEQUENCES 1997: 78-96 - [c20]Harry Buhrman, Lance Fortnow:
Resource-Bounded Kolmogorov Complexity Revisited. STACS 1997: 105-116 - 1996
- [c19]Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi:
Optimal Routing Tables. PODC 1996: 134-142 - [c18]Harry Buhrman, Luc Longpré:
Compressibility and Resource Bounded Measure. STACS 1996: 13-24 - [c17]Harry Buhrman, Thomas Thierauf:
The Complexity of Generating and Checking Proffs of Membership. STACS 1996: 75-86 - 1995
- [c16]Harry Buhrman, Elvira Mayordomo:
An Excursion to the Kolmogorov Random Strings. SCT 1995: 197-203 - [c15]José L. Balcázar, Harry Buhrman, Montserrat Hermo:
Learnability of Kolmogorov-easy circuit expressions via queries. EuroCOLT 1995: 112-124 - [c14]Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Using Autoreducibility to Separate Complexity Classes. FOCS 1995: 520-527 - [c13]Harry Buhrman, Juan A. Garay, Jaap-Henk Hoepman:
Optimal Resiliency against Mobile Faults. FTCS 1995: 83-88 - [c12]Harry Buhrman, Juan A. Garay, Jaap-Henk Hoepman, Mark Moir:
Long-Lived Renaming Made Fast. PODC 1995: 194-203 - [c11]Harry Buhrman, Montserrat Hermo:
On the Sparse Set Conjecture for Sets with Low Denisty. STACS 1995: 609-618 - 1994
- [c10]Harry Buhrman, Jim Kadin, Thomas Thierauf:
On Functions Computable with Nonadaptive Queries to NP. SCT 1994: 43-52 - [c9]Harry Buhrman, Leen Torenvliet:
On the Structure of Complete Sets. SCT 1994: 118-133 - [c8]Harry Buhrman, Pekka Orponen:
Random Strings Make Hard Instances. SCT 1994: 217-222 - [c7]Harry Buhrman, Leen Torenvliet:
On the Cutting Edge of Relativization: The Resource Bounded Injury Method. ICALP 1994: 263-273 - 1993
- [c6]Harry Buhrman, Peter van Helden, Leen Torenvliet:
P-Selective Self-reducibles Sets: A New Characterization of P. SCT 1993: 44-51 - [c5]Harry Buhrman, Luc Longpré, Edith Spaan:
SPARSE reduces conjunctively to TALLY. SCT 1993: 208-214 - [c4]Harry Buhrman, Albrecht Hoene, Leen Torenvliet:
Splittings, Robustness and Structure of Complete Sets. STACS 1993: 175-184 - 1992
- [c3]Harry Buhrman, Edith Spaan, Leen Torenvliet:
Bounded Reductions. Complexity Theory: Current Research 1992: 83-99 - [c2]Harry Buhrman, Steven Homer:
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. FSTTCS 1992: 116-127 - 1991
- [c1]Harry Buhrman, Edith Spaan, Leen Torenvliet:
Bounded Reductions. STACS 1991: 410-421
Parts in Books or Collections
- 2014
- [p2]Harry Buhrman:
Turing in Quantumland. Turing's Legacy 2014: 70-89 - 2001
- [p1]Harry Buhrman:
Quantum Computing and Communication Complexity. Current Trends in Theoretical Computer Science 2001: 664-679
Editorship
- 2008
- [e2]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007. Dagstuhl Seminar Proceedings 07411, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008 [contents] - 2005
- [e1]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005 [contents]
Informal and Other Publications
- 2024
- [i56]Harry Buhrman, Jonas Helsen, Jordi Weggemans:
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians. CoRR abs/2403.04841 (2024) - 2023
- [i55]Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann:
Noisy decoding by shallow circuits with parities: classical and quantum. CoRR abs/2302.02870 (2023) - [i54]Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR abs/2302.10332 (2023) - [i53]Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [i52]Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman:
Memory Compression with Quantum Random-Access Gates. CoRR abs/2203.05599 (2022) - [i51]Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman:
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture. CoRR abs/2207.11068 (2022) - 2021
- [i50]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 abs/2106.02005 (2021) - 2019
- [i49]Harry Buhrman, Subhasree Patro, Florian Speelman:
The Quantum Strong Exponential-Time Hypothesis. CoRR abs/1911.05686 (2019) - 2018
- [i48]Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman:
Round elimination in exact communication complexity. CoRR abs/1812.09290 (2018) - [i47]Harry Buhrman, Floor van de Pavert:
The Case for Quantum Software. ERCIM News 2018(112) (2018) - 2016
- [i46]Harry Buhrman, Matthias Christandl, Jeroen Zuiddam:
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. CoRR abs/1603.03757 (2016) - 2014
- [i45]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. TR14 (2014) - 2012
- [i44]Harry Buhrman, Matthias Christandl, Christian Schaffner:
Complete Insecurity of Quantum Protocols for Classical Two-Party Computation. CoRR abs/1201.0849 (2012) - [i43]Jop Briët, Harry Buhrman, Dion Gijswijt:
Violating the Shannon capacity of metric graphs with entanglement. CoRR abs/1207.1779 (2012) - [i42]Harry Buhrman, David García-Soriano, Arie Matsliah, Ronald de Wolf:
The non-adaptive query complexity of testing k-parities. CoRR abs/1209.3849 (2012) - [i41]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: the resource-bounded case. Electron. Colloquium Comput. Complex. TR12 (2012) - [i40]Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i39]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 abs/1109.2563 (2011) - [i38]Harry Buhrman, Serge Fehr, Christian Schaffner:
Position-Based Quantum Cryptography. ERCIM News 2011(85): 16-17 (2011) - 2010
- [i37]Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner:
Position-Based Quantum Cryptography: Impossibility and Constructions. CoRR abs/1009.2490 (2010) - [i36]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. TR10 (2010) - [i35]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electron. Colloquium Comput. Complex. TR10 (2010) - [i34]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: 275 (2010) - 2009
- [i33]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity 2009 - [i32]Harry Buhrman, David García-Soriano, Arie Matsliah:
Learning Parities in the Mistake-Bound model. Algebraic Methods in Computational Complexity 2009 - [i31]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CoRR abs/0912.3162 (2009) - [i30]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. TR09 (2009) - [i29]Harry Buhrman, David García-Soriano, Arie Matsliah:
Learning parities in the mistake-bound model. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i28]Harry Buhrman, John M. Hitchcock:
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i27]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i26]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i25]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 - [i24]Bram Vermeer, Harry Buhrman:
Quantum Information Processing. ERCIM News 2007(71) (2007) - 2006
- [i23]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. TR06 (2006) - 2004
- [i22]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004 - [i21]Troy Lee, Dieter van Melkebeek, Harry Buhrman:
Language Compression and Pseudorandom Generators. Electron. Colloquium Comput. Complex. TR04 (2004) - [i20]Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet:
Enumerations of the Kolmogorov Function. Electron. Colloquium Comput. Complex. TR04 (2004) - [i19]Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electron. Colloquium Comput. Complex. TR04 (2004) - [i18]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [i17]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity. CoRR cs.CC/0304012 (2003) - [i16]Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig:
Multiparty Quantum Coin Flipping. CoRR quant-ph/0304112 (2003) - [i15]Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Quantum Algorithms and Polynomials. CoRR quant-ph/0309220 (2003) - 2002
- [i14]Harry Buhrman, Alessandro Panconesi, Riccardo Silvestri, Paul M. B. Vitányi:
On the Importance of Having an Identity or, is Consensus really Universal? CoRR cs.DC/0201006 (2002) - [i13]Harry Buhrman, Ronald de Wolf:
Quantum Zero-Error Algorithms Cannot be Composed. CoRR quant-ph/0211029 (2002) - [i12]Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek:
Power from Random Strings. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [i11]Harry Buhrman, John Tromp, Paul M. B. Vitányi:
Time and Space Bounds for Reversible Simulation. CoRR quant-ph/0101133 (2001) - [i10]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection. Electron. Colloquium Comput. Complex. TR01 (2001) - 1999
- [i9]Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka:
Bounds for Small-Error and Zero-Error Quantum Algorithms. CoRR cs.CC/9904019 (1999) - [i8]Harry Buhrman, Ronald de Wolf:
Communication Complexity Lower Bounds by Polynomials. CoRR cs.CC/9910010 (1999) - [i7]Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi:
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method. CoRR cs.DC/9903009 (1999) - [i6]Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi:
Mutual Search. CoRR cs.DS/9902005 (1999) - [i5]Harry Buhrman, Wim van Dam:
Quantum Bounded Query Complexity. CoRR quant-ph/9903035 (1999) - 1998
- [i4]Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi:
New Applications of the Incompressibility Method: Part II. CoRR cs.CC/9809060 (1998) - [i3]Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf:
Quantum Lower Bounds by Polynomials. CoRR quant-ph/9802049 (1998) - [i2]Harry Buhrman, Ronald de Wolf:
Lower Bounds for Quantum Search and Derandomization. CoRR quant-ph/9811046 (1998) - [i1]Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar:
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem. Electron. Colloquium Comput. Complex. TR98 (1998)
Coauthor Index
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-25 05:45 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
