Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Harry Buhrman
2010 – today
- 2013
[j50]Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick: Multipartite entanglement in XOR games. Quantum Information & Computation 13(3-4): 334-360 (2013)- [c77]Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman: The garden-hose model. ITCS 2013: 145-158
- [c76]Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff: Learning Reductions to Sparse Sets. MFCS 2013: 243-253
- 2012
- [j49]Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf: Near-Optimal and Explicit Bell Inequality Violations. Theory of Computing 8(1): 623-645 (2012)
- [c75]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff: Reductions to the Set of Random Strings: The Resource-Bounded Case. MFCS 2012: 88-99
- [i36]Harry Buhrman, Matthias Christandl, Christian Schaffner: Complete Insecurity of Quantum Protocols for Classical Two-Party Computation. CoRR abs/1201.0849 (2012)
- [i35]Jop Briët, Harry Buhrman, Dion Gijswijt: Violating the Shannon capacity of metric graphs with entanglement. CoRR abs/1207.1779 (2012)
- [i34]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)
- [i33]Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff: Reductions to the set of random strings: the resource-bounded case. Electronic Colloquium on Computational Complexity (ECCC) 19: 54 (2012)
- [i32]Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman: Towards a Reverse Newman's Theorem in Interactive Information Complexity. Electronic Colloquium on Computational Complexity (ECCC) 19: 179 (2012)
- 2011
- [j48]Harry Buhrman, Serge Fehr, Christian Schaffner: Position-Based Quantum Cryptography. ERCIM News 2011(85): 16-17 (2011)
- [j47]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. Biology Bioinform. 8(5): 1358-1372 (2011)
- [c74]Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf: Near-Optimal and Explicit Bell Inequality Violations. IEEE Conference on Computational Complexity 2011: 157-166
- [c73]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
- [i31]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)
- 2010
- [j46]Harry Buhrman, David García-Soriano, Arie Matsliah: Learning parities in the mistake-bound model. Inf. Process. Lett. 111(1): 16-21 (2010)
- [j45]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)
- [j44]Harry Buhrman, Benjamin J. Hescott, Steven Homer, Leen Torenvliet: Non-Uniform Reductions. Theory Comput. Syst. 47(2): 317-341 (2010)
- [c72]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. IEEE Conference on Computational Complexity 2010: 58-63
- [i30]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)
- [i29]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin: Sparse Selfreducible Sets and Nonuniform Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 17: 163 (2010)
- [i28]Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek: A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electronic Colloquium on Computational Complexity (ECCC) 17: 174 (2010)
- [i27]Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner: Position-Based Quantum Cryptography: Impossibility and Constructions. IACR Cryptology ePrint Archive 2010: 275 (2010)
2000 – 2009
- 2009
- [c71]Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209
- [i26]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. CoRR abs/0912.3162 (2009)
- [i25]Harry Buhrman, David García-Soriano, Arie Matsliah: Learning parities in the mistake-bound model. Electronic Colloquium on Computational Complexity (ECCC) 16: 60 (2009)
- [i24]Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 64 (2009)
- 2008
- [j43]
- [j42]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)
- [c70]Harry Buhrman, John M. Hitchcock: NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. IEEE Conference on Computational Complexity 2008: 1-7
- [c69]Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin: Randomised Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331
- [e2]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf (Eds.): 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
- [i23]Harry Buhrman, John M. Hitchcock: NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. Electronic Colloquium on Computational Complexity (ECCC) 15(022) (2008)
- 2007
- [j41]
- [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)
- [c68]Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin: High Entropy Random Selection Protocols. APPROX-RANDOM 2007: 366-379
- [c67]Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf: On Computation and Communication with Small Bias. IEEE Conference on Computational Complexity 2007: 24-32
- [c66]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
- [c65]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
- [c64]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
- [c63]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
- [c62]
- 2006
- [j38]Eric Allender, Harry Buhrman, Michal Koucký: What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Logic 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 Computing 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)
- [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]
- [c59]Harry Buhrman, Leen Torenvliet, Falk Unger: Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. STACS 2006: 455-468
- [i22]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting onto functions might not be hard. Electronic Colloquium on Computational Complexity (ECCC) 13(024) (2006)
- 2005
- [j34]Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language compression and pseudorandom generators. Computational Complexity 14(3): 228-255 (2005)
- [j33]Harry Buhrman, Leen Torenvliet: A Post's Program for Complexity Theory. Bulletin of the 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)
- [c58]
- [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
- [e1]Harry Buhrman, Lance Fortnow, Thomas Thierauf (Eds.): Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005
- 2004
- [c55]Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language Compression and Pseudorandom Generators. IEEE Conference on Computational Complexity 2004: 15-28
- [c54]Harry Buhrman, Leen Torenvliet: Separating Complexity Classes Using Structural Properties. IEEE Conference on Computational Complexity 2004: 130-138
- [c53]Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping. IEEE Conference on Computational Complexity 2004: 250-259
- [c52]Harry Buhrman, Lance Fortnow, Thomas Thierauf: 04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004
- [c51]Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi: Individual Communication Complexity: Extended Abstract. STACS 2004: 19-30
- [c50]Eric Allender, Harry Buhrman, Michal Koucký: What Can be Efficiently Reduced to the K-Random Strings? STACS 2004: 584-595
- [i21]Troy Lee, Dieter van Melkebeek, Harry Buhrman: Language Compression and Pseudorandom Generators. Electronic Colloquium on Computational Complexity (ECCC)(002) (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. Electronic Colloquium on Computational Complexity (ECCC)(015) (2004)
- [i19]Eric Allender, Harry Buhrman, Michal Koucký: What Can be Efficiently Reduced to the Kolmogorov-Random Strings? Electronic Colloquium on Computational Complexity (ECCC)(044) (2004)
- [i18]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. Electronic Colloquium on Computational Complexity (ECCC)(081) (2004)
- 2003
- [j30]Harry Buhrman, Ronald de Wolf: Quantum zero-error algorithms cannot be composed. Inf. Process. Lett. 87(2): 79-84 (2003)
- [c49]
- [c48]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum property testing. SODA 2003: 480-488
- [c47]
- [c46]
- [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
- [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)
- [c45]Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger: Power from Random Strings. FOCS 2002: 669-678
- [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. Electronic Colloquium on Computational Complexity (ECCC)(028) (2002)
- 2001
- [j27]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet: Two oracles that force a big crunch. Computational Complexity 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)
- [c44]Harry Buhrman, Ronald de Wolf: Communication Complexity Lower Bounds by Polynomials. IEEE Conference on Computational Complexity 2001: 120-130
- [c43]Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf: Quantum Algorithms for Element Distinctness. IEEE Conference on Computational Complexity 2001: 131-137
- [c42]Harry Buhrman, John Tromp, Paul M. B. Vitányi: Time and Space Bounds for Reversible Simulation. ICALP 2001: 1017-1027
- [p1]Harry Buhrman: Quantum Computing and Communication Complexity. Current Trends in Theoretical Computer Science 2001: 664-679
- [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. Electronic Colloquium on Computational Complexity (ECCC) 8(19) (2001)
- 2000
- [j22]Harry Buhrman: Quantum Computing and Communication Complexity. Bulletin of the 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]
- [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)
- [c41]Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet: The Communication Complexity of Enumeration, Elimination, and Selection. IEEE Conference on Computational Complexity 2000: 44-53
- [c40]Harry Buhrman, Sophie Laplante, Peter Bro Miltersen: New Bounds for the Language Compression Problem. IEEE Conference on Computational Complexity 2000: 126-130
- [c39]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek: Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418
- [c38]Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are bitvectors optimal? STOC 2000: 449-458
- [c37]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
1990 – 1999
- 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]
- [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)
- [c36]Harry Buhrman, Wim van Dam: Quantum Bounded Query Complexity. IEEE Conference on Computational Complexity 1999: 149-
- [c35]Harry Buhrman, Leen Torenvliet: Complicated Complementations. IEEE Conference on Computational Complexity 1999: 227-236
- [c34]Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka: Bounds for Small-Error and Zero-Error Quantum Algorithms. FOCS 1999: 358-368
- [c33]Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi: New Applications of the Incompressibility Method. ICALP 1999: 220-229
- [c32]Harry Buhrman, Lance Fortnow: One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109
- [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]
- 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)
- [c31]Harry Buhrman, Lance Fortnow, Thomas Thierauf: Nonrelativizing Separations. IEEE Conference on Computational Complexity 1998: 8-12
- [c30]
- [c29]Harry Buhrman, Dieter van Melkebeek: Hard Sets are Hard to Find. IEEE Conference on Computational Complexity 1998: 170-181
- [c28]Harry Buhrman, Leen Torenvliet: Randomness is Hard. IEEE Conference on Computational Complexity 1998: 249-260
- [c27]Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf: Quantum Lower Bounds by Polynomials. FOCS 1998: 352-361
- [c26]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
- [c25]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
- [c24]Harry Buhrman, Richard Cleve, Avi Wigderson: Quantum vs. Classical Communication and Computation. STOC 1998: 63-68
- [c23]Richard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208
- [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. Electronic Colloquium on Computational Complexity (ECCC) 5(58) (1998)
- 1997
- [j8]Harry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. J. Comput. Syst. Sci. 54(3): 393-399 (1997)
- [c22]Harry Buhrman, Lance Fortnow, Leen Torenvliet: Six Hypotheses in Search of a Theorem. IEEE Conference on Computational Complexity 1997: 2-12
- [c21]Harry Buhrman, Stephen A. Fenner, Lance Fortnow: Results on Resource-Bounded Measure. ICALP 1997: 188-194
- [c20]
- 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]
- [c19]
- [c18]
- [c17]Harry Buhrman, Thomas Thierauf: The Complexity of Generating and Checking Proffs of Membership. STACS 1996: 75-86
- 1995
- [j4]Harry Buhrman, Edith Hemaspaandra, Luc Longpré: SPARSE Reduces Conjunctively to TALLY. SIAM J. Comput. 24(4): 673-681 (1995)
- [c16]Harry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. Structure in Complexity Theory Conference 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. Structure in Complexity Theory Conference 1994: 43-52
- [c9]Harry Buhrman, Leen Torenvliet: On the Structure of Complete Sets. Structure in Complexity Theory Conference 1994: 118-133
- [c8]Harry Buhrman, Pekka Orponen: Random Strings Make Hard Instances. Structure in Complexity Theory Conference 1994: 217-222
- [c7]Harry Buhrman, Leen Torenvliet: On the Cutting Edge of Relativization: The Resource Bounded Injury Method. ICALP 1994: 263-273
- 1993
- [j3]Harry Buhrman, Edith Spaan, Leen Torenvliet: The Relative Power of Logspace and Polynomial Time Reductions. Computational Complexity 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)
- [c6]Harry Buhrman, Peter van Helden, Leen Torenvliet: P-Selective Self-reducibles Sets: A New Characterization of P. Structure in Complexity Theory Conference 1993: 44-51
- [c5]Harry Buhrman, Luc Longpré, Edith Spaan: SPARSE reduces conjunctively to TALLY. Structure in Complexity Theory Conference 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
- [j1]Harry Buhrman, Steven Homer, Leen Torenvliet: Completeness for Nondeterministic Complexity Classes. Mathematical Systems Theory 24(3): 179-200 (1991)
- [c1]
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:10 CEST by the dblp team