Harry Buhrman - Author Profile

Edit Profile

Buhrman, Harry

Author ID:	buhrman.harry
Published as:	Buhrman, Harry; Buhrman, H.
External Links:	MGP · Wikidata · dblp · GND

Documents Indexed:	120 Publications since 1991, including 1 Additional arXiv Preprint
	1 Contribution as Editor
Co-Authors:	121 Co-Authors with 117 Joint Publications
	2,904 Co-Co-Authors

all top 5

Co-Authors

4	single-authored
23	Fortnow, Lance J.
21	Torenvliet, Leen
12	Vitányi, Paul M. B.
11	Koucký, Michal
10	Loff, Bruno
9	de Wolf, Ronald Michiel
9	Speelman, Florian
9	Vereshchagin, Nikolay K.
8	Briët, Jop
7	van Melkebeek, Dieter
5	Allender, Eric W.
5	Christandl, Matthias
5	Newman, Ilan I.
5	Rohrig, Hein
5	Tromp, John T.
4	Cleve, Richard
4	Fehr, Serge
4	Hemaspaandra, Edith
4	Hoepman, Jaap-Henk
4	Longpré, Luc
4	Schaffner, Christian
4	Unger, Falk
3	Garay, Juan A.
3	Homer, Steven
3	Lee, Troy
3	Li, Ming
3	Piovesan, Teresa
3	Scarpa, Giannicola
3	Thierauf, Thomas
2	Bannink, Tom
2	Beigel, Richard
2	Chandran, Nishanth
2	Fenner, Stephen A.
2	Franklin, Matthew K.
2	Friedman, Luke
2	García-Soriano, David
2	Gelles, Ran
2	Goyal, Vipul
2	Hoene, Albrecht
2	Jiang, Tao
2	Klauck, Hartmut
2	Laurent, Monique
2	Linden, Noah
2	Lotker, Zvi
2	Matsliah, Arie
2	Miltersen, P. B.
2	Ostrovsky, Rafail
2	Panconesi, Alessandro
2	Patro, Subhasree
2	Patt-Shamir, Boaz
2	Pavan, Aduri
2	Radhakrishnan, Jaikumar
2	Rogers, John D.
2	Silvestri, Riccardo
2	Wehner, Stephanie
1	Ambainis, Andris
1	Antunes, Luis
1	Beals, Robert M.
1	Brassard, Gilles
1	Brody, Joshua E.
1	Castro-Silva, Davi
1	Chang, Richard
1	Czekaj, Łukasz
1	Dürr, Christoph
1	Fejer, Peter A.
1	Fenner, Steve
1	Gasarch, William Ian
1	Gijswijt, Dion C.
1	Gilis, Dimitri
1	Gilyén, András Pal
1	Grabowski, Piotr
1	Grudka, Andrzej
1	Hayden, Patrick M.
1	Heiligman, Mark
1	Hermo, Montserrat
1	Hescott, Benjamin J.
1	Hitchcock, John M.
1	Hoepman, Jaap-Henki
1	Horodecki, Michał
1	Horodecki, Paweł
1	Høyer, Peter
1	Kadin, Jim
1	Kalyanasundaram, Bala
1	Labib, Farrokh
1	Laplante, Sophie
1	Leung, Debbie W.
1	Lo, Hoi-Kwong
1	Magniez, Frédéric
1	Mančinska, Laura
1	Markiewicz, Marcin
1	Massar, Serge
1	Matos, Armando B.
1	Mayordomo, Elvira
1	Méthot, André Allan
1	Moir, Mark
1	Montanaro, Ashley
1	Mosca, Michele
1	Muchnik, Andrej A.
1	Neumann, Niels M. P.
1	Orponen, Pekka
...and 21 more Co-Authors

all top 5

Serials

15	SIAM Journal on Computing
8	Journal of Computer and System Sciences
8	Theory of Computing Systems
3	Information Processing Letters
3	Algorithmica
3	Computational Complexity
2	Theoretical Computer Science
2	Proceedings of the National Academy of Sciences of the United States of America
2	Journal of the ACM
2	Bulletin of the European Association for Theoretical Computer Science EATCS
2	Physical Review Letters
1	Communications in Mathematical Physics
1	IEEE Transactions on Information Theory
1	Journal of Statistical Physics
1	Journal of Functional Analysis
1	The Journal of Symbolic Logic
1	Mathematical Systems Theory
1	Annals of Pure and Applied Logic
1	Journal of Physics A: Mathematical and General
1	Distributed Computing
1	Chicago Journal of Theoretical Computer Science
1	Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
1	Logical Methods in Computer Science
1	Theory of Computing
1	Journal of Theoretical Biology

all top 5

Fields

105	Computer science (68-XX)
29	Quantum theory (81-XX)
12	Information and communication theory, circuits (94-XX)
11	Mathematical logic and foundations (03-XX)
2	Combinatorics (05-XX)
2	Linear and multilinear algebra; matrix theory (15-XX)
2	Operations research, mathematical programming (90-XX)
2	Game theory, economics, finance, and other social and behavioral sciences (91-XX)
1	General and overarching topics; collections (00-XX)
1	Order, lattices, ordered algebraic structures (06-XX)
1	Number theory (11-XX)
1	Measure and integration (28-XX)
1	Harmonic analysis on Euclidean spaces (42-XX)
1	Functional analysis (46-XX)
1	Probability theory and stochastic processes (60-XX)
1	Numerical analysis (65-XX)
1	Biology and other natural sciences (92-XX)

Publications by Year

all cited Publications top 5 cited Publications

Citations contained in zbMATH Open

105 Publications have been cited 1,174 times in 868 Documents	Cited by ▼	Year ▼
Complexity measures and decision tree complexity: a survey. Zbl 1061.68058 Buhrman, Harry; de Wolf, Ronald	164	2002
Quantum lower bounds by polynomials. Zbl 1127.68404 Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald	149	2001
Quantum vs. classical communication and computation. Zbl 1028.68056 Buhrman, Harry; Cleve, Richard; Wigderson, Avi	81	1998
Power from random strings. Zbl 1106.68049 Allender, Eric; Buhrman, Harry; Koucký, Michal; van Melkebeek, Dieter; Ronneburger, Detlef	59	2006
Limit on nonlocality in any world in which communication complexity is not trivial. Zbl 1228.81055 Brassard, Gilles; Buhrman, Harry; Linden, Noah; Méthot, André Allan; Tapp, Alain; Unger, Falk	48	2006
Quantum verification of matrix products. Zbl 1192.81056 Buhrman, Harry; Špalek, Robert	32	2006
Quantum algorithms for element distinctness. Zbl 1081.68029 Buhrman, Harry; Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Magniez, Frédéric; Santha, Miklos; de Wolf, Ronald	31	2005
Resource-bounded Kolmogorov complexity revisited. Zbl 1017.68061 Buhrman, Harry; Fortnow, Lance; Laplante, Sophie	26	2002
Nonrelativizing separations. Zbl 0935.68032 Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas	24	1998
Quantum entanglement and communication complexity. Zbl 0980.68051 Buhrman, Harry; Cleve, Richard; van Dam, Wim	20	2001
Are bitvectors optimal? Zbl 1008.68038 Buhrman, H.; Miltersen, P. B.; Radhakrishnan, J.; Venkatesh, S.	19	2002
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034 Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald	17	2012
Robust polynomials and quantum algorithms. Zbl 1121.68049 Buhrman, Harry; Newman, Ilan; Rohrig, Hein; de Wolf, Ronald	17	2007
Quantum property testing. Zbl 1225.68088 Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein	16	2008
Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. Zbl 0925.68183 Buhrman, Harry; Homer, Steven	14	1992
Computing with a full memory: catalytic space. Zbl 1315.68125 Buhrman, Harry; Cleve, Richard; Koucký, Michal; Loff, Bruno; Speelman, Florian	14	2014
Implications of superstrong non-locality for cryptography. Zbl 1149.94305 Buhrman, Harry; Christandl, Matthias; Unger, Falk; Wehner, Stephanie; Winter, Andreas	13	2006
The non-adaptive query complexity of testing \(k\)-parities. Zbl 1286.68487 Buhrman, Harry; García-Soriano, David; Matsliah, Arie; de Wolf, Ronald	13	2013
Are bitvectors optimal? Zbl 1296.68063 Buhrman, H.; Miltersen, P. B.; Radhakrishnan, J.; Venkatesh, S.	12	2000
On the importance of having an identity or, is consensus really universal? Zbl 1264.68026 Buhrman, Harry; Panconesi, Alessandro; Silvestri, Riccardo	12	2005
A generalized Grothendieck inequality and nonlocal correlations that require high entanglement. Zbl 1221.81029 Briët, Jop; Buhrman, Harry; Toner, Ben	12	2011
Enumerations of the Kolmogorov function. Zbl 1165.03025 Beigel, Richard; Buhrman, Harry; Fejer, Peter; Fortnow, Lance; Grabowski, Piotr; Longpré, Luc; Muchnik, Andrej; Stephan, Frank; Torenvliet, Leen	12	2006
Towards a reverse Newman’s theorem in interactive information complexity. Zbl 1353.68073 Brody, Joshua; Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian; Vereshchagin, Nikolay	11	2016
What can be efficiently reduced to the Kolmogorov-random strings? Zbl 1088.03037 Allender, Eric; Buhrman, Harry; Koucký, Michal	11	2006
Position-based quantum cryptography: impossibility and constructions. Zbl 1287.94060 Buhrman, Harry; Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian	11	2011
Position-based quantum cryptography: impossibility and constructions. Zbl 1290.94052 Buhrman, Harry; Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian	11	2014
One-sided versus two-sided error in probabilistic computation. Zbl 0928.68052 Buhrman, Harry; Fortnow, Lance	10	1999
Separating complexity classes using autoreducibility. Zbl 0949.68068 Buhrman, Harry; Fortnow, Lance; van Melkebeek, Dieter; Torenvliet, Leen	10	2000
Distributed quantum computing. Zbl 1124.68361 Buhrman, Harry; Röhrig, Hein	10	2003
Language compression and pseudorandom generators. Zbl 1085.68040 Buhrman, Harry; Lee, Troy; van Melkebeek, Dieter	10	2005
Completeness for nondeterministic complexity classes. Zbl 0745.68046 Buhrman, Harry; Homer, Steven; Torenvliet, Leen	9	1991
Security of quantum bit string commitment depends on the information measure. Zbl 1228.81098 Buhrman, Harry; Christandl, Matthias; Hayden, Patrick; Lo, Hoi-Kwong; Wehner, Stephanie	9	2006
Time and space bounds for reversible simulation (extended abstract). Zbl 0986.68512 Buhrman, Harry; Tromp, John; Vitányi, Paul	8	2001
Long-lived renaming made fast. Zbl 1373.68080 Buhrman, Harry; Garay, Juan A.; Hoepman, Jaap-Henki; Moir, Mark	8	1995
A Post’s program for complexity theory. Zbl 1169.68426 Buhrman, Harry; Torenvliet, Leen	8	2005
Functions computable with nonadaptive queries to NP. Zbl 0893.68069 Buhrman, H.; Kadin, J.; Thierauf, T.	7	1998
Two queries. Zbl 0947.68064 Buhrman, Harry; Fortnow, Lance	7	1999
Splittings, robustness, and structure of complete sets. Zbl 0906.03039 Buhrman, Harry; Hoene, Albrecht; Torenvliet, Leen	7	1998
All Schatten spaces endowed with the Schur product are \(Q\)-algebras. Zbl 1237.46036 Briët, Jop; Buhrman, Harry; Lee, Troy; Vidick, Thomas	7	2012
Quantum communication complexity advantage implies violation of a Bell inequality. Zbl 1355.81046 Buhrman, Harry; Czekaj, Łukasz; Grudka, Andrzej; Horodecki, Michał; Horodecki, Paweł; Markiewicz, Marcin; Speelman, Florian; Strelchuk, Sergii	7	2016
Unconditional lower bounds against advice. Zbl 1248.68212 Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul	7	2009
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. Zbl 1402.68063 Buhrman, Harry; Christandl, Matthias; Zuiddam, Jeroen	7	2017
SPARSE reduces conjunctively to TALLY. Zbl 0830.68042 Buhrman, Harry; Hemaspaandra, Edith; Longpré, Luc	6	1995
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem. Zbl 0963.68230 Buhrman, Harry; van Melkebeek, Dieter; Regan, Kenneth W.; Sivakumar, D.; Strauss, Martin	6	2000
An excursion to the Kolmogorov random strings. Zbl 0882.68077 Buhrman, Harry; Mayordomo, Elvira	6	1997
Time and space bounds for reversible simulation. Zbl 0988.81021 Buhrman, Harry; Tromp, John; Vitányi, Paul	6	2001
NP might not be as easy as detecting unique solutions. Zbl 1027.68607 Beigel, Richard; Buhrman, Harry; Fortnow, Lance	6	1998
\(p\)-selective self-reducible sets: a new characterization of P. Zbl 0859.68032 Buhrman, Harry; Torenvliet, Leen	6	1996
Quantum property testing. Zbl 1092.68615 Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein	6	2003
Quantum computing and communication complexity. Zbl 0973.68070 Buhrman, Harry	5	2000
Increasing Kolmogorov complexity. Zbl 1117.68039 Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Vereshchagin, Nikolai	5	2005
New applications of the incompressibility method. II. Zbl 0943.68083 Buhrman, H.; Jiang, T.; Li, M.; Vitányi, P.	5	2000
On the importance of having an identity or, is consensus really universal? (Extended abstract). Zbl 0987.68507 Buhrman, Harry; Panconesi, Alessandro; Silvestri, Riccardo; Vitanyi, Paul	5	2000
Bounded reductions. Zbl 0788.68049 Buhrman, Harry; Spaan, Edith; Torenvliet, Leen	5	1993
Catalytic space: non-determinism and hierarchy. Zbl 1387.68109 Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian	5	2018
Optimal proof systems and sparse sets. Zbl 0962.68071 Buhrman, Harry; Fenner, Steve; Fortnow, Lance; van Melkebeek, Dieter	4	2000
Hard sets are hard to find. Zbl 0947.68067 Buhrman, Harry; van Melkebeek, Dieter	4	1999
Compressibility and resource bounded measure. Zbl 1015.68082 Buhrman, Harry; Longpré, Luc	4	2002
Kolmogorov random graphs and the incompressibility method. Zbl 0939.68054 Buhrman, Harry; Li, Ming; Tromp, John; Vitányi, Paul	4	1999
The communication complexity of enumeration, elimination, and selection. Zbl 0989.68058 Ambainis, Andris; Buhrman, Harry; Gasarch, William; Kalyanasundaram, Bala; Torenvliet, Leen	4	2001
Some results on derandomization. Zbl 1066.68049 Buhrman, Harry; Fortnow, Lance; Pavan, A.	4	2005
Bounded reductions. Zbl 0773.68029 Buhrman, Harry; Spaan, Edith; Torenvliet, Leen	4	1991
Optimal routing tables. Zbl 1321.68041 Buhrman, Harry; Hoepman, Jaap-Henk; Vitányi, Paul	4	1996
The garden-hose model. Zbl 1360.68458 Buhrman, Harry; Fehr, Serge; Schaffner, Christian; Speelman, Florian	4	2013
Resource-bounded Kolmogorov complexity revisited. Zbl 1498.68129 Buhrman, Harry; Fortnow, Lance	4	1997
Non-uniform reductions. Zbl 1206.68129 Buhrman, Harry; Hescott, Benjamin; Homer, Steven; Torenvliet, Leen	4	2010
Does the polynomial hierarchy collapse if onto functions are invertible? Zbl 1183.68296 Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay	4	2010
Randomness is hard. Zbl 0977.68046 Buhrman, Harry; Torenvliet, Leen	3	2000
Some results on derandomization. Zbl 1035.68052 Buhrman, Harry; Fortnow, Lance; Pavan, A.	3	2003
One bit of advice. Zbl 1035.68051 Buhrman, Harry; Chang, Richard; Fortnow, Lance	3	2003
Random strings make hard instances. Zbl 0859.68034 Buhrman, Harry; Orponen, Pekka	3	1996
A lower bound for quantum search of an ordered list. Zbl 1002.68035 Buhrman, Harry; de Wolf, Ronald	3	1999
Complete sets and structure in subrecursive classes. Zbl 0922.03058 Buhrman, Harry; Torenvliet, Leen	3	1998
Round elimination in exact communication complexity. Zbl 1366.68053 Briët, Jop; Buhrman, Harry; Leung, Debbie; Piovesan, Teresa; Speelman, Florian	3	2015
On the cutting edge of relativization: the resource bounded injury method. Zbl 1420.68090 Buhrman, Harry; Torenvliet, Leen	3	1994
On the parallel repetition of multi-player games: the no-signaling case. Zbl 1359.68083 Buhrman, Harry; Fehr, Serge; Schaffner, Christian	3	2014
Reductions to the set of random strings: the resource-bounded case. Zbl 1338.68125 Allender, Eric; Buhrman, Harry; Friedman, Luke; Loff, Bruno	3	2014
Individual communication complexity. Zbl 1121.68057 Buhrman, Harry; Klauck, Hartmut; Vereshchagin, Nikolai; Vitányi, Paul	3	2007
Compressibility and resource bounded measure. Zbl 1379.68137 Buhrman, Harry; Longpré, Luc	3	1996
The complexity of generating and checking proofs of membership. Zbl 1379.68159 Buhrman, Harry; Thierauf, Thomas	3	1996
Catalytic space: non-determinism and hierarchy. Zbl 1380.68178 Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian	3	2016
Space-efficient routing tables for almost all networks and the incompressibility method. Zbl 0940.68066 Buhrman, Harry; Hoepman, Jaap-Henk; Vitányi, Paul	2	1999
Robust polynomials and quantum algorithms. Zbl 1118.68491 Buhrman, Harry; Newman, Ilan; Röhrig, Hein; de Wolf, Ronald	2	2005
New applications of the incompressibility method. (Extended abstract). Zbl 0939.68055 Buhrman, Harry; Jiang, Tao; Li, Ming; Vitányi, Paul	2	1999
Violating the Shannon capacity of metric graphs with entanglement. Zbl 1292.81015 Briët, Jop; Buhrman, Harry; Gijswijt, Dion	2	2013
Learning parities in the mistake-bound model. Zbl 1260.68188 Buhrman, Harry; García-Soriano, David; Matsliah, Arie	2	2010
Inverting onto functions and polynomial hierarchy. Zbl 1188.68144 Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay	2	2007
The relative power of logspace and polynomial time reductions. Zbl 0801.68063 Buhrman, Harry; Spaan, Edith; Torenvliet, Leen	2	1993
Results on resource-bounded measure. Zbl 1401.68087 Buhrman, Harry; Fenner, Stephen; Fortnow, Lance	2	1997
Mutual search. (Extended abstract). Zbl 0930.68045 Buhrman, Harry; Franklin, Matthew; Garay, Juan A.; Hoepman, Jaap-Henk; Tromp, John; Vitányi, Paul	1	1998
Quantum computing and communication complexity. Zbl 1049.68063 Buhrman, Harry	1	2001
Two queries. Zbl 0935.68033 Buhrman, Harry; Fortnow, Lance	1	1998
Hard sets are hard to find. Zbl 0935.68039 Buhrman, H.; van Melkebeek, D.	1	1998
Entanglement-assisted zero-error source-channel coding. Zbl 1359.81053 Briët, Jop; Buhrman, Harry; Laurent, Monique; Piovesan, Teresa; Scarpa, Giannicola	1	2015
Using autoreducibility to separate complexity classes. Zbl 0938.68667 Buhrman, Harry; Fortnow, Lance; Torenvliet, Leen	1	1995
Reductions to the set of random strings: the resource-bounded case. Zbl 1338.68124 Allender, Eric; Buhrman, Harry; Friedman, Luke; Loff, Bruno	1	2012
Mutual search. Zbl 1065.68617 Buhrman, Harry; Franklin, Matthew; Garay, Juan A.; Hoepman, Jaap-Henk; Tromp, John; Vitányi, Paul	1	1999
High entropy random selection protocols. (Extended abstract). Zbl 1171.68504 Buhrman, Harry; Christandl, Matthias; Koucký, Michal; Lotker, Zvi; Patt-Shamir, Boaz; Vereshchagin, Nikolai	1	2007
Quantum zero-error algorithms cannot be composed. Zbl 1175.68182 Buhrman, Harry; de Wolf, Ronald	1	2003
Zero-error source-channel coding with entanglement. Zbl 1366.81083 Briët, Jop; Buhrman, Harry; Laurent, Monique; Piovesan, Teresa; Scarpa, Giannicola	1	2013
Limits of quantum speed-ups for computational geometry and other problems: fine-grained complexity via quantum walks. Zbl 07829263 Buhrman, Harry; Loff, Bruno; Patro, Subhasree; Speelman, Florian	1	2022
The interaction light cone of the discrete Bak-Sneppen, contact and other local processes. Zbl 1480.60001 Bannink, Tom; Buhrman, Harry; Gilyén, András; Szegedy, Mario	1	2019
Catalytic space: non-determinism and hierarchy. Zbl 1387.68109 Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian	5	2018
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication. Zbl 1402.68063 Buhrman, Harry; Christandl, Matthias; Zuiddam, Jeroen	7	2017
Towards a reverse Newman’s theorem in interactive information complexity. Zbl 1353.68073 Brody, Joshua; Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian; Vereshchagin, Nikolay	11	2016
Quantum communication complexity advantage implies violation of a Bell inequality. Zbl 1355.81046 Buhrman, Harry; Czekaj, Łukasz; Grudka, Andrzej; Horodecki, Michał; Horodecki, Paweł; Markiewicz, Marcin; Speelman, Florian; Strelchuk, Sergii	7	2016
Catalytic space: non-determinism and hierarchy. Zbl 1380.68178 Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian	3	2016
Round elimination in exact communication complexity. Zbl 1366.68053 Briët, Jop; Buhrman, Harry; Leung, Debbie; Piovesan, Teresa; Speelman, Florian	3	2015
Entanglement-assisted zero-error source-channel coding. Zbl 1359.81053 Briët, Jop; Buhrman, Harry; Laurent, Monique; Piovesan, Teresa; Scarpa, Giannicola	1	2015
Hardness of approximation for knapsack problems. Zbl 1328.68073 Buhrman, Harry; Loff, Bruno; Torenvliet, Leen	1	2015
Computing with a full memory: catalytic space. Zbl 1315.68125 Buhrman, Harry; Cleve, Richard; Koucký, Michal; Loff, Bruno; Speelman, Florian	14	2014
Position-based quantum cryptography: impossibility and constructions. Zbl 1290.94052 Buhrman, Harry; Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian	11	2014
On the parallel repetition of multi-player games: the no-signaling case. Zbl 1359.68083 Buhrman, Harry; Fehr, Serge; Schaffner, Christian	3	2014
Reductions to the set of random strings: the resource-bounded case. Zbl 1338.68125 Allender, Eric; Buhrman, Harry; Friedman, Luke; Loff, Bruno	3	2014
The non-adaptive query complexity of testing \(k\)-parities. Zbl 1286.68487 Buhrman, Harry; García-Soriano, David; Matsliah, Arie; de Wolf, Ronald	13	2013
The garden-hose model. Zbl 1360.68458 Buhrman, Harry; Fehr, Serge; Schaffner, Christian; Speelman, Florian	4	2013
Violating the Shannon capacity of metric graphs with entanglement. Zbl 1292.81015 Briët, Jop; Buhrman, Harry; Gijswijt, Dion	2	2013
Zero-error source-channel coding with entanglement. Zbl 1366.81083 Briët, Jop; Buhrman, Harry; Laurent, Monique; Piovesan, Teresa; Scarpa, Giannicola	1	2013
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034 Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald	17	2012
All Schatten spaces endowed with the Schur product are \(Q\)-algebras. Zbl 1237.46036 Briët, Jop; Buhrman, Harry; Lee, Troy; Vidick, Thomas	7	2012
Reductions to the set of random strings: the resource-bounded case. Zbl 1338.68124 Allender, Eric; Buhrman, Harry; Friedman, Luke; Loff, Bruno	1	2012
A generalized Grothendieck inequality and nonlocal correlations that require high entanglement. Zbl 1221.81029 Briët, Jop; Buhrman, Harry; Toner, Ben	12	2011
Position-based quantum cryptography: impossibility and constructions. Zbl 1287.94060 Buhrman, Harry; Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian	11	2011
Non-uniform reductions. Zbl 1206.68129 Buhrman, Harry; Hescott, Benjamin; Homer, Steven; Torenvliet, Leen	4	2010
Does the polynomial hierarchy collapse if onto functions are invertible? Zbl 1183.68296 Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay	4	2010
Learning parities in the mistake-bound model. Zbl 1260.68188 Buhrman, Harry; García-Soriano, David; Matsliah, Arie	2	2010
Unconditional lower bounds against advice. Zbl 1248.68212 Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul	7	2009
Quantum property testing. Zbl 1225.68088 Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein	16	2008
Robust polynomials and quantum algorithms. Zbl 1121.68049 Buhrman, Harry; Newman, Ilan; Rohrig, Hein; de Wolf, Ronald	17	2007
Individual communication complexity. Zbl 1121.68057 Buhrman, Harry; Klauck, Hartmut; Vereshchagin, Nikolai; Vitányi, Paul	3	2007
Inverting onto functions and polynomial hierarchy. Zbl 1188.68144 Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay	2	2007
High entropy random selection protocols. (Extended abstract). Zbl 1171.68504 Buhrman, Harry; Christandl, Matthias; Koucký, Michal; Lotker, Zvi; Patt-Shamir, Boaz; Vereshchagin, Nikolai	1	2007
Power from random strings. Zbl 1106.68049 Allender, Eric; Buhrman, Harry; Koucký, Michal; van Melkebeek, Dieter; Ronneburger, Detlef	59	2006
Limit on nonlocality in any world in which communication complexity is not trivial. Zbl 1228.81055 Brassard, Gilles; Buhrman, Harry; Linden, Noah; Méthot, André Allan; Tapp, Alain; Unger, Falk	48	2006
Quantum verification of matrix products. Zbl 1192.81056 Buhrman, Harry; Špalek, Robert	32	2006
Implications of superstrong non-locality for cryptography. Zbl 1149.94305 Buhrman, Harry; Christandl, Matthias; Unger, Falk; Wehner, Stephanie; Winter, Andreas	13	2006
Enumerations of the Kolmogorov function. Zbl 1165.03025 Beigel, Richard; Buhrman, Harry; Fejer, Peter; Fortnow, Lance; Grabowski, Piotr; Longpré, Luc; Muchnik, Andrej; Stephan, Frank; Torenvliet, Leen	12	2006
What can be efficiently reduced to the Kolmogorov-random strings? Zbl 1088.03037 Allender, Eric; Buhrman, Harry; Koucký, Michal	11	2006
Security of quantum bit string commitment depends on the information measure. Zbl 1228.81098 Buhrman, Harry; Christandl, Matthias; Hayden, Patrick; Lo, Hoi-Kwong; Wehner, Stephanie	9	2006
Quantum algorithms for element distinctness. Zbl 1081.68029 Buhrman, Harry; Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Magniez, Frédéric; Santha, Miklos; de Wolf, Ronald	31	2005
On the importance of having an identity or, is consensus really universal? Zbl 1264.68026 Buhrman, Harry; Panconesi, Alessandro; Silvestri, Riccardo	12	2005
Language compression and pseudorandom generators. Zbl 1085.68040 Buhrman, Harry; Lee, Troy; van Melkebeek, Dieter	10	2005
A Post’s program for complexity theory. Zbl 1169.68426 Buhrman, Harry; Torenvliet, Leen	8	2005
Increasing Kolmogorov complexity. Zbl 1117.68039 Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Vereshchagin, Nikolai	5	2005
Some results on derandomization. Zbl 1066.68049 Buhrman, Harry; Fortnow, Lance; Pavan, A.	4	2005
Robust polynomials and quantum algorithms. Zbl 1118.68491 Buhrman, Harry; Newman, Ilan; Röhrig, Hein; de Wolf, Ronald	2	2005
What can be efficiently reduced to the K-random strings? Zbl 1122.68445 Allender, Eric; Buhrman, Harry; Koucký, Michal	1	2004
Distributed quantum computing. Zbl 1124.68361 Buhrman, Harry; Röhrig, Hein	10	2003
Quantum property testing. Zbl 1092.68615 Buhrman, Harry; Fortnow, Lance; Newman, Ilan; Röhrig, Hein	6	2003
Some results on derandomization. Zbl 1035.68052 Buhrman, Harry; Fortnow, Lance; Pavan, A.	3	2003
One bit of advice. Zbl 1035.68051 Buhrman, Harry; Chang, Richard; Fortnow, Lance	3	2003
Quantum zero-error algorithms cannot be composed. Zbl 1175.68182 Buhrman, Harry; de Wolf, Ronald	1	2003
Complexity measures and decision tree complexity: a survey. Zbl 1061.68058 Buhrman, Harry; de Wolf, Ronald	164	2002
Resource-bounded Kolmogorov complexity revisited. Zbl 1017.68061 Buhrman, Harry; Fortnow, Lance; Laplante, Sophie	26	2002
Are bitvectors optimal? Zbl 1008.68038 Buhrman, H.; Miltersen, P. B.; Radhakrishnan, J.; Venkatesh, S.	19	2002
Compressibility and resource bounded measure. Zbl 1015.68082 Buhrman, Harry; Longpré, Luc	4	2002
Quantum lower bounds by polynomials. Zbl 1127.68404 Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald	149	2001
Quantum entanglement and communication complexity. Zbl 0980.68051 Buhrman, Harry; Cleve, Richard; van Dam, Wim	20	2001
Time and space bounds for reversible simulation (extended abstract). Zbl 0986.68512 Buhrman, Harry; Tromp, John; Vitányi, Paul	8	2001
Time and space bounds for reversible simulation. Zbl 0988.81021 Buhrman, Harry; Tromp, John; Vitányi, Paul	6	2001
The communication complexity of enumeration, elimination, and selection. Zbl 0989.68058 Ambainis, Andris; Buhrman, Harry; Gasarch, William; Kalyanasundaram, Bala; Torenvliet, Leen	4	2001
Quantum computing and communication complexity. Zbl 1049.68063 Buhrman, Harry	1	2001
Are bitvectors optimal? Zbl 1296.68063 Buhrman, H.; Miltersen, P. B.; Radhakrishnan, J.; Venkatesh, S.	12	2000
Separating complexity classes using autoreducibility. Zbl 0949.68068 Buhrman, Harry; Fortnow, Lance; van Melkebeek, Dieter; Torenvliet, Leen	10	2000
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem. Zbl 0963.68230 Buhrman, Harry; van Melkebeek, Dieter; Regan, Kenneth W.; Sivakumar, D.; Strauss, Martin	6	2000
Quantum computing and communication complexity. Zbl 0973.68070 Buhrman, Harry	5	2000
New applications of the incompressibility method. II. Zbl 0943.68083 Buhrman, H.; Jiang, T.; Li, M.; Vitányi, P.	5	2000
On the importance of having an identity or, is consensus really universal? (Extended abstract). Zbl 0987.68507 Buhrman, Harry; Panconesi, Alessandro; Silvestri, Riccardo; Vitanyi, Paul	5	2000
Optimal proof systems and sparse sets. Zbl 0962.68071 Buhrman, Harry; Fenner, Steve; Fortnow, Lance; van Melkebeek, Dieter	4	2000
Randomness is hard. Zbl 0977.68046 Buhrman, Harry; Torenvliet, Leen	3	2000
One-sided versus two-sided error in probabilistic computation. Zbl 0928.68052 Buhrman, Harry; Fortnow, Lance	10	1999
Two queries. Zbl 0947.68064 Buhrman, Harry; Fortnow, Lance	7	1999
Hard sets are hard to find. Zbl 0947.68067 Buhrman, Harry; van Melkebeek, Dieter	4	1999
Kolmogorov random graphs and the incompressibility method. Zbl 0939.68054 Buhrman, Harry; Li, Ming; Tromp, John; Vitányi, Paul	4	1999
A lower bound for quantum search of an ordered list. Zbl 1002.68035 Buhrman, Harry; de Wolf, Ronald	3	1999
Space-efficient routing tables for almost all networks and the incompressibility method. Zbl 0940.68066 Buhrman, Harry; Hoepman, Jaap-Henk; Vitányi, Paul	2	1999
New applications of the incompressibility method. (Extended abstract). Zbl 0939.68055 Buhrman, Harry; Jiang, Tao; Li, Ming; Vitányi, Paul	2	1999
Mutual search. Zbl 1065.68617 Buhrman, Harry; Franklin, Matthew; Garay, Juan A.; Hoepman, Jaap-Henk; Tromp, John; Vitányi, Paul	1	1999
Quantum vs. classical communication and computation. Zbl 1028.68056 Buhrman, Harry; Cleve, Richard; Wigderson, Avi	81	1998
Nonrelativizing separations. Zbl 0935.68032 Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas	24	1998
Functions computable with nonadaptive queries to NP. Zbl 0893.68069 Buhrman, H.; Kadin, J.; Thierauf, T.	7	1998
Splittings, robustness, and structure of complete sets. Zbl 0906.03039 Buhrman, Harry; Hoene, Albrecht; Torenvliet, Leen	7	1998
NP might not be as easy as detecting unique solutions. Zbl 1027.68607 Beigel, Richard; Buhrman, Harry; Fortnow, Lance	6	1998
Complete sets and structure in subrecursive classes. Zbl 0922.03058 Buhrman, Harry; Torenvliet, Leen	3	1998
Mutual search. (Extended abstract). Zbl 0930.68045 Buhrman, Harry; Franklin, Matthew; Garay, Juan A.; Hoepman, Jaap-Henk; Tromp, John; Vitányi, Paul	1	1998
Two queries. Zbl 0935.68033 Buhrman, Harry; Fortnow, Lance	1	1998
Hard sets are hard to find. Zbl 0935.68039 Buhrman, H.; van Melkebeek, D.	1	1998
An excursion to the Kolmogorov random strings. Zbl 0882.68077 Buhrman, Harry; Mayordomo, Elvira	6	1997
Resource-bounded Kolmogorov complexity revisited. Zbl 1498.68129 Buhrman, Harry; Fortnow, Lance	4	1997
Results on resource-bounded measure. Zbl 1401.68087 Buhrman, Harry; Fenner, Stephen; Fortnow, Lance	2	1997
\(p\)-selective self-reducible sets: a new characterization of P. Zbl 0859.68032 Buhrman, Harry; Torenvliet, Leen	6	1996
Optimal routing tables. Zbl 1321.68041 Buhrman, Harry; Hoepman, Jaap-Henk; Vitányi, Paul	4	1996
Random strings make hard instances. Zbl 0859.68034 Buhrman, Harry; Orponen, Pekka	3	1996
Compressibility and resource bounded measure. Zbl 1379.68137 Buhrman, Harry; Longpré, Luc	3	1996
The complexity of generating and checking proofs of membership. Zbl 1379.68159 Buhrman, Harry; Thierauf, Thomas	3	1996
Long-lived renaming made fast. Zbl 1373.68080 Buhrman, Harry; Garay, Juan A.; Hoepman, Jaap-Henki; Moir, Mark	8	1995
SPARSE reduces conjunctively to TALLY. Zbl 0830.68042 Buhrman, Harry; Hemaspaandra, Edith; Longpré, Luc	6	1995
Using autoreducibility to separate complexity classes. Zbl 0938.68667 Buhrman, Harry; Fortnow, Lance; Torenvliet, Leen	1	1995
On the sparse set conjecture for sets with low density. Zbl 1379.68136 Buhrman, Harry; Hermo, Montserrat	1	1995
On the cutting edge of relativization: the resource bounded injury method. Zbl 1420.68090 Buhrman, Harry; Torenvliet, Leen	3	1994
...and 5 more Documents

all cited Publications top 5 cited Publications

all top 5

Cited by 1,138 Authors

24	Ambainis, Andris
20	Allender, Eric W.
19	Buhrman, Harry
16	Kabanets, Valentine
15	Fortnow, Lance J.
14	Le Gall, François
14	Palazuelos, Carlos
13	Tal, Avishay
12	de Wolf, Ronald Michiel
12	Kothari, Robin
12	Qiu, Daowen
12	Santha, Miklos
12	Sherstov, Alexander A.
11	Hitchcock, John M.
11	Sun, Xiaoming
10	Hirahara, Shuichi
10	Köbler, Johannes
9	Aaronson, Scott
9	Glaßer, Christian
9	Impagliazzo, Russell
9	Junge, Marius
9	Pavan, Aduri
8	Christandl, Matthias
8	Göös, Mika
8	Jain, Rahul
8	Lee, Troy
8	Santhanam, Rahul
8	Stephan, Frank
8	Thaler, Justin
7	Gruska, Jozef
7	Ilango, Rahul
7	Klauck, Hartmut
7	Speelman, Florian
7	Vihrovs, Jevgēnijs
7	Vinodchandran, N. Variyam
6	Ben-David, Shalev
6	Bun, Mark
6	Dinesh, Krishnamoorthy
6	Hemaspaandra, Lane A.
6	Koucký, Michal
6	Magniez, Frédéric
6	Mayordomo, Elvira
6	Ogihara, Mitsunori
6	Oliveira, Igor Carboni
6	Romashchenko, Andrei
6	Sarma M. N., Jayalal
6	Selman, Alan Louis
6	Tani, Seiichiro
6	Villanueva, Ignacio
6	Watson, Thomas
6	Williams, Richard Ryan
6	Zhang, Liyu
6	Zheng, Shenggen
6	Zimand, Marius
5	Arvind, Vikraman
5	Belovs, Aleksandrs
5	Braverman, Mark
5	Briët, Jop
5	Brody, Joshua E.
5	Childs, Andrew M.
5	Gál, Anna
5	Grochow, Joshua A.
5	Kesh, Deepanjan
5	Li, Qian
5	Merkle, Wolfgang
5	Musatov, Daniil
5	Nayak, Ashwin
5	Nishimura, Harumichi
5	Pérez-García, David
5	Pitassi, Toniann
5	Ruppert, Eric
5	Sanyal, Swagato
5	Tapp, Alain
5	Torenvliet, Leen
5	van Melkebeek, Dieter
5	Vereshchagin, Nikolay K.
4	Arunachalam, Srinivasan
4	Aspnes, James
4	Beigel, Richard
4	Beyersdorff, Olaf
4	Broadbent, Anne
4	Chakraborty, Sankardeep
4	Chattopadhyay, Arkadev
4	Chen, Lijie
4	Cleve, Richard
4	Downey, Rodney Graham
4	Gavoille, Cyril
4	Iwama, Kazuo
4	Jeffery, Stacey
4	Kawachi, Akinori
4	Kerenidis, Iordanis
4	Kozachinskiy, Alexander
4	Kundu, Srijita
4	Li, Lvzhou
4	Loff, Bruno
4	May, Alex
4	Montanaro, Ashley
4	Moser, Philippe
4	Moshkov, Mikhail Ju.
4	Mundhenk, Martin
...and 1,038 more Authors

all top 5

Cited in 118 Serials

84	Theoretical Computer Science
37	Information Processing Letters
36	Quantum Information Processing
34	Journal of Computer and System Sciences
32	Computational Complexity
32	Theory of Computing Systems
28	Information and Computation
24	SIAM Journal on Computing
24	Algorithmica
19	New Journal of Physics
16	Communications in Mathematical Physics
15	Distributed Computing
14	Journal of Physics A: Mathematical and Theoretical
8	Discrete Applied Mathematics
8	Journal of Mathematical Physics
7	ACM Transactions on Computation Theory
6	International Journal of Theoretical Physics
5	Physics Letters. A
5	Combinatorica
5	Journal of Complexity
5	International Journal of Foundations of Computer Science
5	Chicago Journal of Theoretical Computer Science
5	Natural Computing
5	Theory of Computing
4	Artificial Intelligence
4	Physica A
4	Transactions of the American Mathematical Society
4	Annals of Pure and Applied Logic
4	Mathematical Structures in Computer Science
4	International Journal of Quantum Information
4	Foundations of Physics
3	The Journal of Symbolic Logic
3	Journal of the ACM
3	Annals of Mathematics. Second Series
3	Journal of High Energy Physics
2	Letters in Mathematical Physics
2	Reviews of Modern Physics
2	Journal of Combinatorial Theory. Series B
2	Synthese
2	Journal of Computer Science and Technology
2	New Generation Computing
2	Designs, Codes and Cryptography
2	Bulletin of the American Mathematical Society. New Series
2	Annals of Mathematics and Artificial Intelligence
2	Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
2	Physical Review Letters
2	Foundations and Trends in Theoretical Computer Science
2	Science China. Information Sciences
2	Annalen der Physik
2	Forum of Mathematics, Sigma
2	TheoretiCS
1	Modern Physics Letters A
1	International Journal of Modern Physics A
1	Acta Informatica
1	Communications on Pure and Applied Mathematics
1	Discrete Mathematics
1	Israel Journal of Mathematics
1	Journal of Mathematical Analysis and Applications
1	Journal of Statistical Physics
1	Linear and Multilinear Algebra
1	Mathematical Notes
1	Automatica
1	Computing
1	Journal of Approximation Theory
1	Journal of Combinatorial Theory. Series A
1	Journal of Functional Analysis
1	Journal of Graph Theory
1	Mathematics and Computers in Simulation
1	Mathematical Systems Theory
1	Numerische Mathematik
1	Proceedings of the American Mathematical Society
1	Proceedings of the Edinburgh Mathematical Society. Series II
1	Proceedings of the London Mathematical Society. Third Series
1	Optimal Control Applications & Methods
1	European Journal of Combinatorics
1	Statistics & Probability Letters
1	Journal of Cryptology
1	International Journal of Mathematics
1	Random Structures & Algorithms
1	International Journal of Algebra and Computation
1	Annals of Physics
1	Linear Algebra and its Applications
1	Proceedings of the National Academy of Sciences of the United States of America
1	SIAM Review
1	RAIRO. Informatique Théorique et Applications
1	Archive for Mathematical Logic
1	Mathematical Programming. Series A. Series B
1	SIAM Journal on Optimization
1	The Australasian Journal of Combinatorics
1	New Zealand Journal of Mathematics
1	Journal of Algebraic Combinatorics
1	Journal of Mathematical Sciences (New York)
1	Mathematical Logic Quarterly (MLQ)
1	Journal of Functional Programming
1	Advances in Computational Mathematics
1	Journal of Combinatorial Optimization
1	PAA. Pattern Analysis and Applications
1	Discrete Mathematics and Theoretical Computer Science. DMTCS
1	Revista Matemática Complutense
1	RAIRO. Theoretical Informatics and Applications
...and 18 more Serials

all top 5

Cited in 42 Fields

664	Computer science (68-XX)
260	Quantum theory (81-XX)
111	Information and communication theory, circuits (94-XX)
66	Mathematical logic and foundations (03-XX)
61	Combinatorics (05-XX)
38	Order, lattices, ordered algebraic structures (06-XX)
26	Game theory, economics, finance, and other social and behavioral sciences (91-XX)
24	Operations research, mathematical programming (90-XX)
18	Functional analysis (46-XX)
16	Linear and multilinear algebra; matrix theory (15-XX)
13	Probability theory and stochastic processes (60-XX)
11	Group theory and generalizations (20-XX)
9	Statistical mechanics, structure of matter (82-XX)
8	Numerical analysis (65-XX)
7	Statistics (62-XX)
6	Operator theory (47-XX)
5	Number theory (11-XX)
5	Measure and integration (28-XX)
4	Algebraic geometry (14-XX)
4	Approximations and expansions (41-XX)
4	Relativity and gravitational theory (83-XX)
3	Commutative algebra (13-XX)
3	Dynamical systems and ergodic theory (37-XX)
3	Mechanics of particles and systems (70-XX)
2	Field theory and polynomials (12-XX)
2	Convex and discrete geometry (52-XX)
2	Systems theory; control (93-XX)
1	General and overarching topics; collections (00-XX)
1	Topological groups, Lie groups (22-XX)
1	Real functions (26-XX)
1	Functions of a complex variable (30-XX)
1	Several complex variables and analytic spaces (32-XX)
1	Special functions (33-XX)
1	Ordinary differential equations (34-XX)
1	Partial differential equations (35-XX)
1	Harmonic analysis on Euclidean spaces (42-XX)
1	Abstract harmonic analysis (43-XX)
1	Geometry (51-XX)
1	Global analysis, analysis on manifolds (58-XX)
1	Fluid mechanics (76-XX)
1	Classical thermodynamics, heat transfer (80-XX)
1	Biology and other natural sciences (92-XX)

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.