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.

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

    2023

    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, January 9-11, 2017, Berkeley, CA, USA Article 24 (Leibniz International Proceedings in Informatics; Vol. 67). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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 für Informatik. 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 für Informatik. 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 für Informatik. 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

    2019

    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