Zobrazeno 1 - 10
of 146
pro vyhledávání: '"Harry Buhrman"'
Publikováno v:
Quantum, Vol 8, p 1387 (2024)
Non-local quantum computation (NLQC) is a cheating strategy for position-verification schemes, and has appeared in the context of the AdS/CFT correspondence. Here, we connect NLQC to the wider context of information theoretic cryptography by relating
Externí odkaz:
https://doaj.org/article/f70197a901944d4b89a63483a1f6aac8
Autor:
Antonio Acín, Immanuel Bloch, Harry Buhrman, Tommaso Calarco, Christopher Eichler, Jens Eisert, Daniel Esteve, Nicolas Gisin, Steffen J Glaser, Fedor Jelezko, Stefan Kuhr, Maciej Lewenstein, Max F Riedel, Piet O Schmidt, Rob Thew, Andreas Wallraff, Ian Walmsley, Frank K Wilhelm
Publikováno v:
New Journal of Physics, Vol 20, Iss 8, p 080201 (2018)
Within the last two decades, quantum technologies (QT) have made tremendous progress, moving from Nobel Prize award-winning experiments on quantum physics (1997: Chu, Cohen-Tanoudji, Phillips; 2001: Cornell, Ketterle, Wieman; 2005: Hall, Hänsch-, Gl
Externí odkaz:
https://doaj.org/article/a290024b91b146e2a2217b931e52f361
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 3 (2014)
This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out in [Allender et al] to settle this conje
Externí odkaz:
https://doaj.org/article/466a7f61f6cd45faa1220c986ef2bcd5
Autor:
Nikolay Vereshchagin, Harry Buhrman, Boaz Patt-Shamir, Michal Koucký, Matthias Christandl, Zvi Lotker
Publikováno v:
Algorithmica, 83, 667-694
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques ISBN: 9783540742074
APPROX-RANDOM
Buhrman, H, Christandl, M, Koucky, M, Lotker, Z, Patt-Shamir, B & Vereshchagin, N 2021, ' High Entropy Random Selection Protocols ', Algorithmica, vol. 83, no. 2, pp. 667-694 . https://doi.org/10.1007/s00453-020-00770-y
ResearcherID
APPROX-RANDOM, 366-379
STARTPAGE=366;ENDPAGE=379;TITLE=APPROX-RANDOM
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques ISBN: 9783540742074
APPROX-RANDOM
Buhrman, H, Christandl, M, Koucky, M, Lotker, Z, Patt-Shamir, B & Vereshchagin, N 2021, ' High Entropy Random Selection Protocols ', Algorithmica, vol. 83, no. 2, pp. 667-694 . https://doi.org/10.1007/s00453-020-00770-y
ResearcherID
APPROX-RANDOM, 366-379
STARTPAGE=366;ENDPAGE=379;TITLE=APPROX-RANDOM
We study the two party problem of randomly selecting a common string among all the strings of length n. We want the protocol to have the property that the output distribution has high Shannon entropy or high min entropy, even when one of the two part
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ede455e81db9fd0231a4d86afe623542
https://ir.cwi.nl/pub/30057
https://ir.cwi.nl/pub/30057
Publikováno v:
Algorithmica, 81, 179-200
It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are set
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::467c8c59e6141f14da90edd757f7f44b
https://ir.cwi.nl/pub/27793
https://ir.cwi.nl/pub/27793
Autor:
Florian Speelman, Michal Koucky, Joshua Brody, Harry Buhrman, Bruno Loff, Nikolay Vereshchagin
Publikováno v:
IEEE Conference on Computational Complexity
Algorithmica, 76(3), 749-781. Springer New York
CCC 2013 : 2013 IEEE Conference on Computational Complexity: proceedings : 5-7 June 2013, Palo Alto, California, USA, 24-33
STARTPAGE=24;ENDPAGE=33;TITLE=CCC 2013 : 2013 IEEE Conference on Computational Complexity
Algorithmica, 76(3), 749-781
Brody, J E, Buhrman, H, Koucký, M, Loff, B & Speelman, F 2016, ' Towards a Reverse Newman's Theorem in Interactive Information Complexity ', Algorithmica, vol. 76, no. 3, pp. 749-781 . https://doi.org/10.1007/s00453-015-0112-9
Algorithmica, 76(3), 749-781. Springer New York
CCC 2013 : 2013 IEEE Conference on Computational Complexity: proceedings : 5-7 June 2013, Palo Alto, California, USA, 24-33
STARTPAGE=24;ENDPAGE=33;TITLE=CCC 2013 : 2013 IEEE Conference on Computational Complexity
Algorithmica, 76(3), 749-781
Brody, J E, Buhrman, H, Koucký, M, Loff, B & Speelman, F 2016, ' Towards a Reverse Newman's Theorem in Interactive Information Complexity ', Algorithmica, vol. 76, no. 3, pp. 749-781 . https://doi.org/10.1007/s00453-015-0112-9
Newman's theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with but a little increase in communication complexity. We consider a reversed scenario in the context of inform
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a9ad693dd6ce93447badab2b800bff93
https://ir.cwi.nl/pub/25098
https://ir.cwi.nl/pub/25098
Autor:
Florian Speelman, Andrzej Grudka, Paweł Horodecki, Łukasz Czekaj, Harry Buhrman, Marcin Markiewicz, Michał Horodecki, Sergii Strelchuk
Publikováno v:
Proceedings of the National Academy of Sciences of the United States of America, 113(12), 3191-3196
Proceedings of the National Academy of Sciences of the United States of America, 113(12), 3191-3196. National Academy of Sciences
Proceedings of the National Academy of Sciences of the United States of America, 113(12), 3191-3196. National Academy of Sciences
We obtain a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol offering a (sufficiently large) quantum advantage in communication complexity, there exists a way of obtaining me
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1d7cb6f1e6dbc2359fc59d1b08d3665d
https://doi.org/10.1073/pnas.1507647113
https://doi.org/10.1073/pnas.1507647113
Publikováno v:
IEEE Transactions on Information Theory, 61(2), 1124-1138
IEEE Transactions on Information Theory, 61(2), 1124-1138. Institute of Electrical and Electronics Engineers Inc.
IEEE Transactions on Information Theory, 61(2), 1124-1138. Institute of Electrical and Electronics Engineers Inc.
We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given correlated inputs from a random source. Their goal is for Bob to learn Ali
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9ff87faafdaa5ae2305f742c5154f55d
https://doi.org/10.1109/tit.2014.2385080
https://doi.org/10.1109/tit.2014.2385080
Publikováno v:
Theory of Computing Systems, 56(2), 372-393
Theory of Computing Systems
Theory of Computing Systems, 56(2), 372-393. Springer New York
Theory of Computing Systems
Theory of Computing Systems, 56(2), 372-393. Springer New York
We show various hardness results for knapsack and related problems; in particular we will show that unless the Exponential-Time Hypothesis is false, subset-sum cannot be approximated any better than with an FPTAS. We also provide new unconditional lo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6910cca7d10a033660db5de60a95809b
https://doi.org/10.1007/s00224-014-9550-z
https://doi.org/10.1007/s00224-014-9550-z
Publikováno v:
Physical Review Letters, 117(230503), 230503-1-230503-5
Physical Review Letters, 117(23):230503. American Physical Society
Physical Review Letters, 117(23):230503. American Physical Society
By how much must the communication complexity of a function increase if we demand that the parties not only correctly compute the function but also return all registers (other than the one containing the answer) to their initial states at the end of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14c40665584e00d1599a3264a0fd6480
https://doi.org/10.1103/physrevlett.117.230503
https://doi.org/10.1103/physrevlett.117.230503