For best experience please turn on javascript and use a modern browser!
You are using a browser that is no longer supported by Microsoft. Please upgrade your browser. The site may not present itself correctly if you continue browsing.
uva.nl
Korteweg-de Vries Institute for Mathematics Korteweg-de Vries Institute for Mathematics

Prof. dr. H.M. (Harry) Buhrman

Faculty of Science
ILLC
Visiting address
  • Science Park 105
  • Room number: F2.08
Postal address
  • Postbus 94242
    1090 GE Amsterdam
Contact details
  • Publications

    2022

    • Buhrman, H., Loff, B., Patro, S., & Speelman, F. (2022). Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. In M. Braverman (Ed.), 13th Innovations in Theoretical Computer Science Conference: ITCS 2022, January 31-February 3, 2022, Berkeley, CA, USA Article 31 (Leibniz International Proceedings in Informatics; Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2022.31 [details]
    • Buhrman, H., Loff, B., Patro, S., & Speelman, F. (2022). Memory Compression with Quantum Random-Access Gates. In F. Le Gall, & T. Morimae (Eds.), 17th Conference on the Theory of Quantum Computation, Communication and Cryptography: TQC 2022, July 11–15, 2022, Urbana Champaign, Illinois, USA Article 10 (Leibniz International Proceedings in Informatics; Vol. 232). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.TQC.2022.10 [details]

    2021

    • Buhrman, H., Patro, S., & Speelman, F. (2021). A Framework of Quantum Strong Exponential-Time Hypotheses. In M. Bläser, & B. Monmege (Eds.), 38th International Symposium on Theoretical Aspects of Computer Science: STACS 2021, March 16–19, 2021, Saarbrücken, Germany (Virtual Conference) Article 19 (Leibniz International Proceedings in Informatics; Vol. 187). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2021.19 [details]

    2019

    2018

    2017

    • Buhrman, H., Christandl, M., & Zuiddam, J. (2017). Nondeterministic quantum communication complexity: The cyclic equality game and iterated matrix multiplication. In C. H. Papadimitriou (Ed.), 8th Innovations in Theoretical Computer Science Conference: ICTS 2017, Januar 9-11, 2017, Berkeley, CA, USA Article 24 (Leibniz International Proceedings in Informatics; Vol. 67). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2017.24 [details]

    2016

    • Antunes, L., Buhrman, H., Matos, A., Souto, A., & Teixeira, A. (2016). Distinguishing Two Probability Ensembles with One Sample from each Ensemble. Theory of Computing Systems, 59(3), 517-531. Advance online publication. https://doi.org/10.1007/s00224-015-9661-1 [details]
    • Brody, J., Buhrman, H., Koucký, M., Loff, B., Speelman, F., & Vereshchagin, N. (2016). Towards a Reverse Newman's Theorem in Interactive Information Complexity. Algorithmica, 76(3), 749-781. Advance online publication. https://doi.org/10.1007/s00453-015-0112-9 [details]
    • Buhrman, H., Christandl, M., Perry, C., & Zuiddam, J. (2016). Clean Quantum and Classical Communication Protocols. Physical Review Letters, 117(23), Article 230503. https://doi.org/10.1103/PhysRevLett.117.230503 [details]
    • Buhrman, H., Czekaj, Ł., Grudka, A., Horodecki, M., Horodecki, P., Markiewicz, M., Speelman, F., & Strelchuk, S. (2016). Quantum communication complexity advantage implies violation of a Bell inequality. Proceedings of the National Academy of Sciences of the United States of America, 113(12), 3191-3196. https://doi.org/10.1073/pnas.1507647113 [details]
    • Buhrman, H., Koucký, M., Loff, B., & Speelman, F. (2016). Catalytic space: Non-determinism and hierarchy. In N. Ollinger, & H. Vollmer (Eds.), 33rd Symposium on Theoretical Aspects of Computer Science: STACS'16, February 17-20, 2016, Orléans, France Article 24 (Leibniz International Proceedings in Informatics; Vol. 47). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2016.24 [details]

    2015

    • Briët, J., Buhrman, H., Laurent, M., Piovesan, T., & Scarpa, G. (2015). Entanglement-assisted zero-error source-channel coding. IEEE Transactions on Information Theory, 61(2), 1124-1138. Advance online publication. https://doi.org/10.1109/TIT.2014.2385080 [details]
    • Briët, J., Buhrman, H., Leung, D., Piovesan, T., & Speelman, F. (2015). Round Elimination in Exact Communication Complexity. In S. Beigi, & R. König (Eds.), 10th Conference on the Theory of Quantum Computation, Communication and Cryptography: TQC'15, May 20-22, 2015, Brussels, Belgium (pp. 206-225). (Leibniz International Proceedings in Informatics; Vol. 44). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.TQC.2015.206 [details]
    • Buhrman, H., Loff, B., & Torenvliet, L. (2015). Hardness of approximation for Knapsack problems. Theory of Computing Systems, 56(2), 372-393. Advance online publication. https://doi.org/10.1007/s00224-014-9550-z [details]

    2014

    • Allender, E., Buhrman, H., Friedman, L., & Loff, B. (2014). Reductions to the set of random strings: The resource-bounded case. Logical Methods in Computer Science, 10(3), Article 5. https://doi.org/10.2168/LMCS-10(3:5)2014 [details]
    • Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., & Schaffner, C. (2014). Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43(1), 150-178. https://doi.org/10.1137/130913687 [details]
    • Buhrman, H., Cleve, R., Koucký, M., Loff, B., & Speelman, F. (2014). Computing with a full memory: Catalytic space. In STOC '14: proceedings of the 2014 ACM Symposium on Theory of Computing : New York, New York, USA, May 31, 2014-June 3, 2014 (pp. 857-866). ACM. https://doi.org/10.1145/2591796.2591874 [details]
    • Buhrman, H., Fehr, S., & Schaffner, C. (2014). On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. In S. T. Flammia, & A. W. Harrow (Eds.), 9th Conference on the Theory of Quantum Computation, Communication and Cryptography: TQC 2014, May 21-23, 2014, National University of Singapore, Singapore (pp. 24-35). (Leibniz International Proceedings in Informatics; Vol. 27). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.TQC.2014.24 [details]

    2013

    • Briët, J., Buhrman, H., & Gijswijt, D. (2013). Violating the Shannon capacity of metric graphs with entanglement. Proceedings of the National Academy of Sciences of the United States of America, 110(48), 19227-19232. https://doi.org/10.1073/pnas.1203857110 [details]
    • Briët, J., Buhrman, H., Lee, T., & Vidick, T. (2013). Multipartite entanglement in XOR games. Quantum Information & Computation, 13(3&4), 334-360. https://doi.org/10.26421/QIC13.3-4 [details]
    • Brody, J., Buhrman, H., Koucký, M., Loff, B., Speelman, F., & Vereshchagin, N. (2013). Towards a reverse Newman's theorem in interactive information complexity. In CCC 2013 : 2013 IEEE Conference on Computational Complexity: proceedings : 5-7 June 2013, Palo Alto, California, USA (pp. 24-33). IEEE. https://doi.org/10.1109/CCC.2013.12 [details]
    • Buhrman, H., Fehr, S., Schaffner, C., & Speelman, F. (2013). The Garden-Hose Model. In ITCS'13: proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science : January 9-12, 2013, Berkeley, California, USA (pp. 145-157). Association for Computing Machinery. https://doi.org/10.1145/2422436.2422455 [details]
    • Buhrman, H., Fortnow, L., Hitchcock, J. M., & Loff, B. (2013). Learning reductions to sparse sets. In K. Chatterjee, & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013 : proceedings (pp. 243-253). (Lecture Notes in Computer Science; Vol. 8087). Springer. https://doi.org/10.1007/978-3-642-40313-2_23 [details]
    • Buhrman, H., García-Soriano, D., Matsliah, A., & de Wolf, R. (2013). The non-adaptive query complexity of testing k-parities. Chicago Journal of Theoretical Computer Science, 2013, Article 6. https://doi.org/10.4086/cjtcs.2013.006 [details]
    • Buhrman, H., van der Gulik, P. T. S., Klau, G. W., Schaffner, C., Speijer, D., & Stougie, L. (2013). A Realistic Model Under Which the Genetic Code is Optimal. Journal of molecular evolution, 77(4), 170-184. Advance online publication. https://doi.org/10.1007/s00239-013-9571-2 [details]

    2012

    2011

    • Briët, J., Buhrman, H., & Toner, B. (2011). A Generalized Grothendieck Inequality and Nonlocal Correlations that Require High Entanglement. Communications in Mathematical Physics, 305(3), 827-843. https://doi.org/10.1007/s00220-011-1280-3 [details]
    • Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., & Schaffner, C. (2011). Position-based quantum cryptography: impossibility and constructions. In P. Rogaway (Ed.), Advances in Cryptology – CRYPTO 2011: 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011: proceedings (pp. 429-446). (Lecture Notes in Computer Science; Vol. 6841). Springer. https://doi.org/10.1007/978-3-642-22792-9_24 [details]
    • Buhrman, H., Regev, O., Scarpa, G., & de Wolf, R. (2011). Near-Optimal and Explicit Bell Inequality Violations. In 26th IEEE Conference on Computational Complexity: proceedings : San Jose, California, 8-10 June 2011 (pp. 157-166). IEEE Computer Society. https://doi.org/10.1109/CCC.2011.30 [details]
    • Buhrman, H., van der Gulik, P. T. S., Kelk, S. M., Koolen, W. M., & Stougie, L. (2011). Some mathematical refinements concerning error minimization in the genetic code. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5), 1358-1372. https://doi.org/10.1109/TCBB.2011.40 [details]

    2010

    2009

    • Allcock, J., Buhrman, H., & Linden, N. (2009). Arbitrarily little knowledge can give a quantum advantage for nonlocal tasks. Physical Review A, 80(3), 032105. https://doi.org/10.1103/PhysRevA.80.032105 [details]
    • Buhrman, H., Fortnow, L., & Santhanam, R. (2009). Unconditional lower bounds against advice. In S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, & W. Thomas (Eds.), Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009 : proceedings (Vol. I, pp. 195-209). (Lecture Notes in Computer Science; Vol. 5555). Springer. https://doi.org/10.1007/978-3-642-02927-1_18 [details]
    • van der Gulik, P., Massar, S., Gilis, D., Buhrman, H., & Rooman, M. (2009). The first peptides: The evolutionary transition between prebiotic amino acids and early proteins. Journal of Theoretical Biology, 261(4), 531-539. https://doi.org/10.1016/j.jtbi.2009.09.004 [details]

    2008

    2007

    • Buhrman, H. M., Christandl, M., Koucký, M., Lotker, Z., Patt-Shamir, B., & Vereshchagin, N. K. (2007). High Entropy Random Selection Protocols. In APPROX-RANDOM (pp. 366-379) [details]
    • Buhrman, H. M., Fortnow, L., Koucký, M., Rogers, J., & Vereshchagin, N. K. (2007). Inverting Onto Functions and Polynomial Hierarchy. In Computer Science - Theory and Applications (pp. 92-103). (Lecture Notes in Computer Science; No. 4649). Springer. [details]
    • Buhrman, H. M., Klauck, H., Vereshchagin, N. K., & Vitanyi, P. M. B. (2007). Individual communication complexity. Journal of Computer and System Sciences, 73, 973-985. https://doi.org/10.1016/j.jcss.2007.03.015 [details]
    • Buhrman, H. M., Newman, I., Röhrig, H. P., & de Wolf, R. M. (2007). Robust Polynomials and Quantum Algorithms. Journal of Computer and System Sciences, 40(4), 379-395. [details]
    • Buhrman, H. M., Vereshchagin, N. K., & de Wolf, R. M. (2007). On Computation and Communication with Small Bias. In Proceedings of the XXII Annual IEEE Conference of Computational Complexity (pp. 24-32) [details]

    2006

    • Allender, E., Buhrman, H. M., & Koucky, M. (2006). What can be efficiently reduced to the kolmogorov-random strings? Annals of Pure and Applied Logic, 138(1-3), 2-19. https://doi.org/10.1016/j.apal.2005.06.003 [details]
    • Allender, E., Buhrman, H. M., Koucky, M., van Melkebeek, D., & Ronneburger, D. (2006). Power from random strings. SIAM Journal on Computing, 35(6), 1467-1493. https://doi.org/10.1137/050628994 [details]
    • Beigel, R., Buhrman, H. M., Feijer, P., Fortnow, L., Grabowski, P., Longpre, L., ... Torenvliet, L. (2006). Enumerations of the Kolmogorov Function. Journal of Symbolic Logic, 7, 501-528. [details]
    • Brassard, G., Buhrman, H. M., Linden, N., Méthot, A. A., Tap, A., & Unger, F. P. (2006). Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial. Physical Review Letters, 96, 250401. http://prl.aps.org/ [details]
    • Buhrman, H. M., & Spalek, R. (2006). Quantum Verification of Matrix Products. In Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06) (pp. 880-889). Miami: ACM Press. [details]
    • Buhrman, H. M., Christandl, M., Hayden, P., H.-K., L., & Wehner, S. D. C. (2006). Security of quantum bit string commitment depends on the information measure. Physical Review Letters, 97, 250501. http://www.arxiv.org/abs/quant-ph/0609237 [details]
    • Buhrman, H. M., Christandl, M., Unger, F. P., Wehner, S. D. C., & WInter, A. (2006). Implications of superstrong non-locality for cryptography. In Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Vol. 462, pp. 1919-1932) [details]
    • Buhrman, H. M., Cleve, R., Laurent, M., Linden, N., Schrijver, A., & Unger, F. P. (2006). New limits on fault-tolerant quantum computation. In 47th Annual IEEE Symposium on Foundations of Computer Science (pp. 411-419) [details]
    • Buhrman, H. M., Torenvliet, L., & Unger, F. P. (2006). Spare Self-reducible sets and polynomial size circuit lower bounds. In Proceedings of STACS 2006 (pp. 455-468). Springer. [details]
    • Buhrman, H., Høyer, P., Röhrig, H., & Massar, S. (2006). Multipartite nonlocal quantum correlations resistant to imperfections. Physical Review A - Atomic, Molecular, and Optical Physics, 73(1), Article 012321. https://doi.org/10.1103/PhysRevA.73.012321
    • Buhrman, H., Torenvliet, L., & Unger, F. (2006). Sparse selfreducible sets and polynomial size circuit lower bounds. In STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 455-468). (Lecture Notes in Computer Science; Vol. 3884). Springer. https://doi.org/10.1007/11672142_37

    2022

    2016

    • Buhrman, H., Czekaj, Ł., Grudka, A., Horodecki, M., Horodecki, P., Markiewicz, M., Speelman, F., & Strelchuk, S. (2016). Erratum: Quantum communication complexity advantage implies violation of a Bell inequality. Proceedings of the National Academy of Sciences of the United States of America, 113(21), Article E3050. https://doi.org/10.1073/pnas.1606259113

    2008

    2006

    • Buhrman, H. M. (2006). Toveren met kwantum informatie. In B. Mols (Ed.), Het raadsel van informatie (pp. 95-113). (7; No. 6). Boom. [details]
    This list of publications is extracted from the UvA-Current Research Information System. Questions? Ask the library or the Pure staff of your faculty / institute. Log in to Pure to edit your publications. Log in to Personal Page Publication Selection tool to manage the visibility of your publications on this list.
  • Ancillary activities
    • Max Planck Institute for quantum optics
      Member Scientific Advisory board
    • Fermioniq
      scientific advisor en co-founder
    • European Research Council
      review panels for starting & consolidator grants
    • commenius leergang
      geven van een lecture over quantum computing en en impact op maatschappij.
    • Institute for Quantum Computing (IQC)
      member scientific advisory board
    • WACT
      member scientific advisor board
    • CIFAR
      member scientific advisory committee
    • INTRIQ
      member advisory board
    • Quantinuum
      Chief scientist quantum algorithms and innovation
edit contact information   edit profile page