For best experience please turn on javascript and use a modern browser!
uva.nl

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

    2018

    • Buhrman, H., Koucký, M., Loff, B., & Speelman, F. (2018). Catalytic Space: Non-determinism and Hierarchy. Theory of Computing Systems, 62(1), 116-135. DOI: 10.1007/s00224-017-9784-7 [details]

    2017

    • Buhrman, H., Christandl, M., & Zuiddam, J. (2017). Nondeterministic quantum communication complexity: The cyclic equality game and iterated matrix multiplication. Leibniz International Proceedings in Informatics, 67, [24]. DOI: 10.4230/LIPIcs.ITCS.2017.24 [details]

    2016

    • 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]
    • 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. DOI: 10.1007/s00453-015-0112-9 [details]
    • Buhrman, H., Czekaj, Ł., Grudka, A., Horodecki, M., Horodecki, P., Markiewicz, M., ... 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. Leibniz International Proceedings in Informatics, 47, [24]. DOI: 10.4230/LIPIcs.STACS.2016.24 [details]
    • 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]

    2015

    2014

    • 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. DOI: 10.1137/130913687 [details]
    • Buhrman, H., Fehr, S., & Schaffner, C. (2014). On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. Leibniz International Proceedings in Informatics, 27, 24-35. DOI: 10.4230/LIPIcs.TQC.2014.24 [details]
    • 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]. DOI: 10.2168/LMCS-10(3:5)2014 [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]
    • 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. DOI: 10.1007/s00239-013-9571-2 [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]
    • Buhrman, H., Fehr, S., Schaffner, C., & Speelman, F. (2013). The Garden-Hose Model. In ITCS 2013: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (pp. 145-158). ACM. DOI: 10.1145/2422436.2422455
    • 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. DOI: 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]. DOI: 10.4086/cjtcs.2013.006 [details]
    • Brody, J., Buhrman, H., Koucky, M., Loff, B., Speelman, F., & Vereshchagin, N. (2013). Towards a reverse Newman's theorem in interactive information complexity. In Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013 (pp. 24-33). [6597746] IEEE. DOI: 10.1109/CCC.2013.12

    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. DOI: 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). Heidelberg: Springer. DOI: 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. DOI: 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. DOI: 10.1109/TCBB.2011.40 [details]

    2010

    2009

    • Buhrman, H., Fortnow, L., & Santhanam, R. (2009). Unconditional lower bounds against advice. Lecture Notes in Computer Science, 5555, 195-209. DOI: 10.1007/978-3-642-02927-1_18 [details]
    • 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]
    • 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. DOI: 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., 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]
    • Buhrman, H., Fortnow, L., Newman, I., & Röhrig, H. (2008). Quantum property testing. SIAM Journal on Computing, 37(5), 1387-1400. DOI: 10.1137/S0097539704442416 [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., 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]
    • 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]

    2006

    • 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]. DOI: 10.1103/PhysRevA.73.012321
    • 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., & 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., 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., 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. DOI: 10.1007/11672142_37
    • 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. DOI: 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]

    2016

    • Buhrman, H., Czekaj, Ł., Grudka, A., Horodecki, M., Horodecki, P., Markiewicz, M., ... 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
    No known ancillary activities