Harry Buhrman | Academic Influence

Harry Buhrman's AcademicInfluence.com Rankings

Harry Buhrman

Computer Science

#2193

World Rank

#2282

Historical Rank

Database

#7217

World Rank

#7465

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Harry Buhrman's Degrees

PhD Computer Science University of Amsterdam
Masters Mathematics University of Amsterdam

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Harry Buhrman Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Harry Buhrman is a Dutch computer scientist, currently Professor of algorithms, complexity theory, and quantum computing at the University of Amsterdam , group leader of the Quantum Computing Group at the Centrum Wiskunde & Informatica , and executive director of QuSoft, the Dutch research center for quantum software.

(See a Problem?)

Harry Buhrman's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Quantum fingerprinting. (2001) (839)
Quantum lower bounds by polynomials (1998) (765)
Complexity measures and decision tree complexity: a survey (2002) (602)
Nonlocality and communication complexity (2009) (446)
Quantum vs. classical communication and computation (1998) (418)
SUBSTITUTING QUANTUM ENTANGLEMENT FOR COMMUNICATION (1997) (342)
Limit on nonlocality in any world in which communication complexity is not trivial. (2005) (307)
The quantum technologies roadmap: a European community view (2018) (256)
The European Quantum Technologies Roadmap (2017) (190)
Quantum algorithms for element distinctness (2000) (174)
Quantum verification of matrix products (2004) (169)
Bounds for small-error and zero-error quantum algorithms (1999) (157)
Power from random strings (2002) (143)
Communication complexity lower bounds by polynomials (1999) (139)
Are bitvectors optimal? (2000) (124)
Quantum Entanglement and Communication Complexity (1997) (123)
Position-Based Quantum Cryptography: Impossibility and Constructions (2011) (116)
Multiparty quantum communication complexity. (1997) (114)
On Computation and Communication with Small Bias (2007) (112)
Nonrelativizing separations (1998) (93)
Quantum Computing and Communication Complexity (2001) (86)
Multiparty quantum coin flipping (2003) (81)
The first peptides: the evolutionary transition between prebiotic amino acids and early proteins. (2009) (79)
Resource-Bounded Kolmogorov Complexity Revisited (1997) (79)
Time and Space Bounds for Reversible Simulation (2001) (75)
Near-Optimal and Explicit Bell Inequality Violations (2011) (69)
Distributed Quantum Computing (2003) (68)
Robust Polynomials and Quantum Algorithms (2003) (64)
New Limits on Fault-Tolerant Quantum Computation (2006) (61)
Complete insecurity of quantum protocols for classical two-party computation Buhrman, (2012) (57)
Position-Based Quantum Cryptography: Impossibility and Constructions (2010) (57)
Quantum property testing (2002) (57)
Implications of superstrong non-locality for cryptography (2005) (56)
Possibility, impossibility, and cheat sensitivity of quantum-bit string commitment (2005) (54)
On the structure of complete sets (1994) (49)
P-selective self-reducibles sets: a new characterization of P (1993) (48)
Causality and Tsirelson's bounds (2004) (47)
Quantum communication complexity advantage implies violation of a Bell inequality (2015) (46)
Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy (1992) (46)
What can be efficiently reduced to the Kolmogorov-random strings? (2006) (46)
Computing with a full memory: catalytic space (2014) (46)
Towards a Reverse Newman’s Theorem in Interactive Information Complexity (2012) (45)
Kolmogorov Random Graphs and the Incompressibility Method (1999) (44)
On the importance of having an identity or, is consensus really universal? (2000) (40)
An excursion to the Kolmogorov random strings (1995) (39)
A pr 2 00 5 Implications of Superstrong Nonlocality for Cryptography (2008) (38)
Two queries (1998) (37)
SPARSE reduces conjunctively to TALLY (1993) (36)
A Generalized Grothendieck Inequality and Nonlocal Correlations that Require High Entanglement (2011) (36)
The non-adaptive query complexity of testing k-parities (2012) (33)
One-sided Versus Two-sided Error in Probabilistic Computation (1999) (32)
Using autoreducibility to separate complexity classes (1995) (32)
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly (2008) (30)
NP might not be as easy as detecting unique solutions (1997) (30)
The garden-hose model (2011) (30)
Separating Complexity Classes Using Autoreducibility (1998) (30)
UvA-DARE (Digital Academic Repository) Complete insecurity of quantum protocols for classical two-party computation Complete Insecurity of Quantum Protocols for Classical Two-Party Computation (2012) (30)
Combinatorics and quantum nonlocality. (2002) (29)
Violating the Shannon capacity of metric graphs with entanglement (2012) (29)
Security of quantum bit string commitment depends on the information measure. (2006) (29)
Optimal resiliency against mobile faults (1995) (27)
Enumerations of the Kolmogorov function (2006) (26)
Long-lived renaming made fast (1995) (26)
A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem (2000) (24)
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case (2013) (24)
Twenty Questions to a P-Selector (1993) (24)
Derandomizing from Random Strings (2009) (23)
Compressibility and Resource Bounded Measure (1996) (23)
Position-Based Quantum Cryptography (2010) (23)
Bounded Reductions (1991) (23)
Classical simulation of entanglement swapping with bounded communication. (2012) (23)
Entanglement-Assisted Zero-Error Source-Channel Coding (2013) (22)
Increasing Kolmogorov Complexity (2005) (22)
Hard sets are hard to find (1998) (21)
MULTIPLAYER XOR GAMES AND QUANTUM COMMUNICATION COMPLEXITY WITH CLIQUE-WISE ENTANGLEMENT (2009) (21)
A generalized Grothendieck inequality and entanglement in XOR games (2009) (21)
Multipartite entanglement in XOR games (2013) (20)
Functions Computable with Nonadaptive Queries to NP (1994) (20)
Some Results on Derandomization (2003) (20)
Resource bounded reductions (1993) (20)
Language compression and pseudorandom generators (2004) (20)
New applications of the incompressibility method: Part II (1998) (19)
Unconditional Lower Bounds against Advice (2009) (19)
On the (Im)Possibility of Quantum String Commitment (2005) (18)
Random strings make hard instances (1994) (18)
Robust Quantum Algorithms and Polynomials (2003) (18)
Optimal routing tables (1996) (17)
Complete Sets and Structure in Subrecursive Classes (1996) (17)
Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method (1999) (17)
Lower Bounds for Quantum Search and Derandomization (1998) (17)
Some Mathematical Refinements Concerning Error Minimization in the Genetic Code (2009) (17)
A Post's Program for Complexity Theory (2005) (16)
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication (2016) (16)
Reductions to the Set of Random Strings: The Resource-Bounded Case (2014) (16)
A Lower Bound for Quantum Search of an Ordered List (1999) (16)
Mutual search (1999) (16)
Randomness is hard (1998) (14)
On the Cutting Edge of Relativization: The Resource Bounded Injury Method (1994) (14)
Splittings, Robustness, and Structure of Complete Sets (1998) (14)
Optimal Proof Systems and Sparse Sets (2000) (14)
Near-Optimal and Explicit Bell Inequality Violations (2010) (14)
The communication complexity of enumeration, elimination, and selection (2000) (14)
Six hypotheses in search of a theorem (1997) (13)
Completeness for nondeterministic complexity classes (1991) (13)
One-sided Versus Two-sided Randomness (1998) (13)
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract) (1998) (13)
Quantum bounded query complexity (1999) (13)
A Framework of Quantum Strong Exponential-Time Hypotheses (2021) (13)
Randomised Individual Communication Complexity (2008) (12)
Zero-error source-channel coding with entanglement. (2013) (12)
New bounds for the language compression problem (2000) (12)
Catalytic Space: Non-determinism and Hierarchy (2017) (12)
A Realistic Model Under Which the Genetic Code is Optimal (2013) (11)
The Complexity of Generating and Checking Proffs of Membership (1996) (11)
A short note on Shor's factoring algorithm (1996) (11)
P-Selective Self-Reducible Sets (1996) (11)
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly (2008) (11)
Round Elimination in Exact Communication Complexity (2018) (10)
Separating complexity classes using structural properties (2004) (10)
All Schatten spaces endowed with the Schur product are Q-algebras (2012) (9)
High Entropy Random Selection Protocols (2007) (8)
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks (2021) (8)
The Garden-Hose Game: A New Model of Computation, and Application to Position-Based Quantum Cryptography (2011) (8)
Non-Uniform Reductions (2010) (8)
Individual communication complexity (2003) (7)
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? (2009) (7)
Position-Based Quantum Cryptography and the Garden-Hose Game (2012) (7)
The Quantum Strong Exponential-Time Hypothesis (2019) (7)
Two oracles that force a big crunch (2002) (7)
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games (2010) (7)
Complicated complementations (1999) (7)
Hardness of Approximation for Knapsack Problems (2015) (7)
One Bit of Advice (2003) (7)
ar X iv : 0 90 7 . 35 84 v 1 [ qu an t-ph ] 2 1 Ju l 2 00 9 Non-locality and Communication Complexity (2009) (7)
Learning parities in the mistake-bound model (2010) (6)
Quantum zero-error algorithms cannot be composed (2002) (6)
Multipartite nonlocal quantum correlations resistant to imperfections (2004) (6)
The relative power of logspace and polynomial time reductions (1993) (6)
What Can be Efficiently Reduced to the K-Random Strings? (2004) (6)
Memory Compression with Quantum Random-Access Gates (2022) (5)
New Protocols and Ideas for Practical Quantum Position Verification (2021) (5)
Splittings, Robustness and Structure of Complete Sets (1993) (5)
Distinguishing Complexity and Symmetry of Information (1995) (5)
Learnability of Kolmogorov-easy circuit expressions via queries (1995) (5)
Better Non-Local Games from Hidden Matching (2010) (5)
Results on Resource-Bounded Measure (1997) (4)
A mathematical model of kinetoplastid mitochondrial gene scrambling advantage (2013) (4)
Reductions to the set of random strings: the resource-bounded case (2012) (4)
Quantum Algorithms for Finding Claws, Collisions and Triangles (2000) (3)
Inverting Onto Functions and Polynomial Hierarchy (2007) (3)
Towards a Reverse Newman’s Theorem in Interactive Information Complexity (2013) (3)
I'm sorry, Dave. I'm afraid I can't do that (2011) (3)
Individual Communication Complexity: Extended Abstract (2004) (3)
Algorithms and Complexity (2000) (3)
On the Role of Quantum Communication and Loss in Attacks on Quantum Position Verification (2022) (3)
On the Sparse Set Conjecture for Sets with Low Denisty (1995) (2)
Using autoreducibility in separating complexity classes (1995) (2)
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem (2023) (2)
Towards practical and error-robust quantum position verification (2021) (2)
One-sided two-sided error in probabilistic computation (1999) (2)
Bounding Quantum-Classical Separations for Classes of Nonlocal Games (2018) (2)
Catalytic Space : Nondeterminism and Hierarchy (2015) (2)
Separations between Shannon capacity and zero error entanglement assisted capacity (2011) (2)
Learning Reductions to Sparse Sets (2013) (2)
The quantum technologies roadmap (2018) (1)
Multipartite nonlocal quantum correlations resistant to imperfections (9 pages) (2006) (1)
Correction for Buhrman et al., Quantum communication complexity advantage implies violation of a Bell inequality (2016) (1)
Arbitrarily little knowledge can give a quantum advantage for nonlocal tasks (2009) (1)
Clean Quantum and Classical Communication Protocols. (2016) (1)
Quantum Ngerprinting (2001) (1)
The Garden-Hose Game and Application to Position-Based Quantum Cryptography (2011) (1)
Quantum Majority Vote (2022) (1)
Catalytic Space: Non-determinism and Hierarchy (2017) (1)
The Interaction Light Cone of the Discrete Bak–Sneppen, Contact and other local processes (2019) (1)
Communication complexity: Eyal Kushilevitz, Noam Nisan, Cambridge University Press, Cambridge, 1997. ISBN 0-56067-5 (1999) (1)
The stage between prebiotic amino acids and early proteins (2009) (1)
Approximation algorithms and hardness of approximation for knapsack problems (2012) (1)
9th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2014, May 21-23, 2014, Singapore (2014) (1)
Noisy decoding by shallow circuits with parities: classical and quantum (2023) (1)
Definability in the degrees of randomness (1985) (1)
Edinburgh Research Explorer Unconditional Lower Bounds against Advice (2009) (0)
UvA-DARE ( Digital Academic Repository ) Round Elimination in Exact Communication (2015) (0)
Inverting onto functions might not be hard (2006) (0)
Two Results on Resource-bounded Measure (1996) (0)
Algebraic Methods in Computational Complexity, 10.-15. October 2004 (2005) (0)
Kolmogorov complexity research and PhD defence of T. Lee (2006) (0)
Mutual Search (Extended Abstract) (1998) (0)
Learning Weak Reductions to Sparse Sets (2012) (0)
Algorithmics and complexity theory (2001) (0)
UvA-DARE (Digital Academic Repository) Round Elimination in Exact Communication Complexity (2015) (0)
The Case for Quantum Software (2018) (0)
UvA-DARE ( Digital Academic Repository ) Catalytic space : Nondeterminism and hierarchy (2016) (0)
UvA-DARE (Digital Academic Repository) Non-uniform reductions (2010) (0)
How Far Are We from Proving Circuit Size Lower Bounds ? (2008) (0)
UvA-DARE (Digital Academic Repository) Clean Quantum and Classical Communication Protocols (2016) (0)
New applications of the incompressibility method (extended abstract) (1999) (0)
Reductions to the set of random strings Allender (2014) (0)
Sparse Selfreducible Sets and Nonuniform Lower Bounds (2018) (0)
Complete sets under non-adaptive reductions are scarce (1997) (0)
A generalized Grothendieck inequality which lower bounds the entanglement required to play nonlocal games (2010) (0)
Quantum Information Processing (2007) (0)
Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421) (2021) (0)
Quantum Pascal's triangle and Sierpinski's carpet (2017) (0)
UvA-DARE ( Digital Academic Repository ) Near-Optimal and Explicit Bell Inequality (2012) (0)
Quantum Computing Moore's Law (0)
Time and Space Bounds for Reversible Simulation ? (Extended Abstract) (2001) (0)
UvA-DARE (Digital Academic Repository) Catalytic space: Non-determinism and hierarchy (2016) (0)
Quantum Entanglement and Communication Complexity Wim Van Dam (1998) (0)
Some mathematicals refinements concerning error minimizatiion in the genetic code. (2010) (0)
Algebraic Methods in Computational Complexity 3 Formula Size Lower Bounds and Quantum States (2005) (0)
A Realistic Model Under Which the Genetic Code is Optimal (2013) (0)
UvA-DARE ( Digital Academic Repository ) On the Parallel Repetition of Multi-Player Games : The No-Signaling (2014) (0)
UvA-DARE (Digital Academic Round Elimination in Exact Communication Complexity (2015) (0)
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds (2006) (0)
A problem of Varopoulos: Schatten spaces with the Schur product are Q-algebras (2011) (0)
Hard Sets Are Hard to Find 1 (2005) (0)
Presentation Evaluation Committee PNA6 (2011) (0)
Foreword (2008) (0)
A generalized Grothendieck constant and nonlocal games that require high entanglement (2011) (0)
Walking the Graph of Language : On a Framework for Meaning and Analogy (2012) (0)
Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 (2008) (0)
Quantum communication (2005) (0)
High Entropy Random Selection Protocols (Extended Abstract) (2008) (0)
A survey of classical simulation methods for quantum computation (2008) (0)
Sparse Selfreducible Sets and Nonuniform Lower Bounds (2018) (0)
Quantum Computing Research and PhD defence of R. Špalek (2006) (0)
2 3 0 Ju n 20 05 Causality and Cirel ’ son bounds (2018) (0)
Distinguishing Two Probability Ensembles with One Sample from each Ensemble (2015) (0)
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture (2022) (0)
Quantum Computing (2005) (0)
Kolmogorov random graphs (1997) (0)
Workshop on Quantum Information, 5-9 (2022) (0)
UvA-DARE (Digital Academic Repository) Multipartite entanglement in XOR games (2018) (0)
High Entropy Random Selection Protocols (2020) (0)
The missing link between prebiotic amino acids and early proteins (2009) (0)
UvA-DARE (Digital Academic Repository) Classical simulation of entanglement swapping with bounded communication Branciard, (2012) (0)
Grothendieck inequalities , nonlocal games and optimization (2011) (0)
Turing in Quantumland (2014) (0)
Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I (2009) (0)
Distinguishing Two Probability Ensembles with One Sample from each Ensemble (2016) (0)
UvA-DARE (Digital Academic Repository) Entanglement-assisted zero-error source-channel coding (2015) (0)
UvA-DARE (Digital Academic Repository) Quantum property testing (2008) (0)
UvA-DARE ( Digital Academic Repository ) Causality and Tsirelson ' s Bounds Buhrman (2005) (0)
UvA-DARE (Digital Academic Repository) Near-Optimal and Explicit Bell Inequality Violations (2012) (0)
Hardness of Approximation for Knapsack Problems (2014) (0)

This paper list is powered by the following services:

Other Resources About Harry Buhrman

en.wikipedia.org

What Schools Are Affiliated With Harry Buhrman?

Harry Buhrman is affiliated with the following schools: