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
  • Publications

    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) [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 [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. 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. 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), [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 [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. 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. 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), [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 and 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). Heidelberg: 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, [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. 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). Los Alamitos, Calif.: 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). Berlin: 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

    • Buhrman, H., & Hitchcock, J. M. (2008). NP-hard sets are exponentially dense unless coNP C NP/poly. In CCC 2008: Twenty-third Annual IEEE Conference on Computational Complexity: Proceedings: 23-26 June 2008, College Park, Maryland (pp. 1-7). Los Alamitos, CA: IEEE Computer Society. [details]
    • Buhrman, H., Fortnow, L., Newman, I., & Röhrig, H. (2008). Quantum property testing. SIAM Journal on Computing, 37(5), 1387-1400. https://doi.org/10.1137/S0097539704442416 [details]
    • Buhrman, H., Koucký, M., & Vereshchagin, N. (2008). Randomised individual communication complexity. In CCC 2008: Twenty-third Annual IEEE Conference on Computational Complexity: Proceedings: 23-26 June 2008, College Park, Maryland (pp. 321-331). Los Alamitos, CA: IEEE Computer Society. [details]

    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). Berlin / Heidelberg: 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. [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. [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). Marseille: 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), [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

    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), [E3050]. https://doi.org/10.1073/pnas.1606259113

    2008

    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
    • European Research Council
      review panels for starting & consolidator grants
    • Institute for Quantum Computing (IQC)
      member scientific advisory board
    • WACT
      member scientific advisor board
    • CIFAR
      member scientific advisory committee
    • INTRIQ
      member advisory board
    • Max Planck Institute for quantum optics
      Member Scientific Advisory board