首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)
  • 本地全文:下载
  • 作者:Noga Ron-Zewi ; Ronen Shaltiel ; Nithin Varma
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2021
  • 卷号:185
  • 页码:33:1-33:18
  • DOI:10.4230/LIPIcs.ITCS.2021.33
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:A binary code Enc:{0,1}^k â†' {0,1}ⁿ is (1/2-ε,L)-list decodable if for every w â^^ {0,1}ⁿ, there exists a set List(w) of size at most L, containing all messages m â^^ {0,1}^k such that the relative Hamming distance between Enc(m) and w is at most 1/2-ε. A q-query local list-decoder for Enc is a randomized procedure Dec that when given oracle access to a string w, makes at most q oracle calls, and for every message m â^^ List(w), with high probability, there exists j â^^ [L] such that for every i â^^ [k], with high probability, Dec^w(i,j) = m_i. We prove lower bounds on q, that apply even if L is huge (say L = 2^{k^{0.9}}) and the rate of Enc is small (meaning that n ≥ 2^{k}): - For ε = 1/k^{ν} for some constant 0 < ν < 1, we prove a lower bound of q = Ω(log(1/δ)/ε²), where δ is the error probability of the local list-decoder. This bound is tight as there is a matching upper bound by Goldreich and Levin (STOC 1989) of q = O(log(1/δ)/ε²) for the Hadamard code (which has n = 2^k). This bound extends an earlier work of Grinberg, Shaltiel and Viola (FOCS 2018) which only works if n ≤ 2^{k^ν} and the number of coins tossed by Dec is small (and therefore does not apply to the Hadamard code, or other codes with low rate). - For smaller ε, we prove a lower bound of roughly q = Ω(1/(â^Sε)). To the best of our knowledge, this is the first lower bound on the number of queries of local list-decoders that gives q ≥ k for small ε. Local list-decoders with small ε form the key component in the celebrated theorem of Goldreich and Levin that extracts a hard-core predicate from a one-way function. We show that black-box proofs cannot improve the Goldreich-Levin theorem and produce a hard-core predicate that is hard to predict with probability 1/2 1/ð"^ω(1) when provided with a one-way function f:{0,1}^ð" â†' {0,1}^ð", where f is such that circuits of size poly(ð") cannot invert f with probability ρ = 1/2^â^Sð" (or even ρ = 1/2^Ω(ð")). This limitation applies to any proof by black-box reduction (even if the reduction is allowed to use nonuniformity and has oracle access to f).
  • 关键词:Local list-decoding; Hard-core predicates; Black-box reduction; Hadamard code
国家哲学社会科学文献中心版权所有