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
2020 – today
- 2023
[c85]Harry Buhrman, Noah Linden, Laura Mancinska
, Ashley Montanaro, Maris Ozols:
Quantum Majority Vote. ITCS 2023: 29:1-29:1- [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
- [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 - [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
- [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) - [c82]Harry Buhrman, Subhasree Patro, Florian Speelman:
A Framework of Quantum Strong Exponential-Time Hypotheses. STACS 2021: 19:1-19:19 - [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)
2010 – 2019
- 2019
- [j57]Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin:
Sparse Selfreducible Sets and Nonuniform Lower Bounds. Algorithmica 81(1): 179-200 (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 - [i49]Harry Buhrman, Subhasree Patro, Florian Speelman:
The Quantum Strong Exponential-Time Hypothesis. CoRR abs/1911.05686 (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) - [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) - 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
- [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) - [c79]Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Catalytic Space: Non-determinism and Hierarchy. STACS 2016: 24:1-24:13 - [i46]Harry Buhrman, Matthias Christandl, Jeroen Zuiddam:
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. CoRR abs/1603.03757 (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) - [c78]Jop Briët, Harry Buhrman, Debbie W. Leung, Teresa Piovesan, Florian Speelman:
Round Elimination in Exact Communication Complexity. TQC 2015: 206-225 - 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) - [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 - [p2]Harry Buhrman:
Turing in Quantumland. Turing's Legacy 2014: 70-89 - [i45]Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: Catalytic space. Electron. Colloquium Comput. Complex. TR14 (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) - [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
- [j47]Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf:
Near-Optimal and Explicit Bell Inequality Violations. Theory Comput. 8(1): 623-645 (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 - [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
- [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) - [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 - [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
- [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) - [c69]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CCC 2010: 58-63 - [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)
2000 – 2009
- 2009
- [c68]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209 - [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
- [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) - [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 - [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] - [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
- [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) - [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 - [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
- [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) - [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 - [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) - 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) - [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 - [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] - 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 - [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
- [j30]Harry Buhrman, Ronald de Wolf:
Quantum zero-error algorithms cannot be composed. Inf. Process. Lett. 87(2): 79-84 (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 - [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) - [c46]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. Electron. Colloquium Comput. Complex. TR02 (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]