Zobrazeno 1 - 10
of 25
pro vyhledávání: '"Tom Gur"'
Publikováno v:
Quantum, Vol 6, p 834 (2022)
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA $\textit{proofs of proximity}$ (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proo
Externí odkaz:
https://doaj.org/article/a2b4d27e79564ad39d2c1c806c09657b
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::45eecbb970ef395a62ebf181965281f5
https://doi.org/10.1137/1.9781611977585.ch26
https://doi.org/10.1137/1.9781611977585.ch26
Publikováno v:
Advances in Cryptology – EUROCRYPT 2023 ISBN: 9783031306167
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::923922a35f1c7c3c72dcf2f1ff1c7eb7
https://doi.org/10.1007/978-3-031-30617-4_13
https://doi.org/10.1007/978-3-031-30617-4_13
Autor:
Tom Gur, Igor Shinkar
Publikováno v:
IEEE Transactions on Information Theory. 66:2904-2911
A $(k,\varepsilon)$-non-malleable extractor is a function ${\sf nmExt} : \{0,1\}^n \times \{0,1\}^d \to \{0,1\}$ that takes two inputs, a weak source $X \sim \{0,1\}^n$ of min-entropy $k$ and an independent uniform seed $s \in \{0,1\}^d$, and outputs
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e2f836d686f3cc8449b97dc476398277
https://doi.org/10.1109/tit.2019.2946896
https://doi.org/10.1109/tit.2019.2946896
Publikováno v:
Theory of Computing. 16:1-68
Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have foun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a111d1f6dcf9f482a4c7589ce171fed1
https://doi.org/10.4086/toc.2020.v016a018
https://doi.org/10.4086/toc.2020.v016a018
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c6e853a629a154458b62c9ce852ea578
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8dfa1699412e78c6beef0e7c1914c62a
http://arxiv.org/abs/2105.03697
http://arxiv.org/abs/2105.03697
Publikováno v:
SODA
Locally correctable codes (LCCs) are error correcting codes C : \Sigmak \rightarrow \Sigman which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. For systematic codes, this notion i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b358b8c2fed4a0906b52efd73a04bc66
http://wrap.warwick.ac.uk/153964/1/WRAP-Relaxed-correctable-codes-linear-block-length-constant-query-complexit-2021.pdf
http://wrap.warwick.ac.uk/153964/1/WRAP-Relaxed-correctable-codes-linear-block-length-constant-query-complexit-2021.pdf
Publikováno v:
ACM-SIAM Symposium on Discrete Algorithms (SODA21)
We prove a general structural theorem for a wide family of local algorithms, which includes\ud property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of\ud every algorithm that makes q adaptive queries and satisfi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d6d50ed77fdff1cd3a13eaa82cffdda1
https://doi.org/10.1137/1.9781611976465.100
https://doi.org/10.1137/1.9781611976465.100
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let C be a class of polynomial-size concepts, and suppose that C can be PAC-learned with membership queries under the uniform d
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bf599bc36bf5651cadfaea38ee88ca67
https://hal.archives-ouvertes.fr/hal-03040161
https://hal.archives-ouvertes.fr/hal-03040161