English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A binary code Enc : {0, 1} → {0, 1} is ( 12 − , 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} such that the relative Hamming distance between Enc(m) and w is at most 12 − . A q-query local list-decoder is a randomized procedure 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(i, j) = mi. We prove lower bounds on q, that apply even if L is huge (say L = 2 0.9 ) and the rate of Enc is small (meaning that n ≥ 2): • For = 1/k for some constant ν > 0, we prove a lower bound of q = Ω( log(1/δ) 2 ), 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/δ) 2 ) for the Hadamard code (which has n = 2 ). This bound extends an earlier work of Grinberg, Shaltiel and Viola (FOCS 2018) which only works if n ≤ 2kν 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 √ ). 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 12 + 1 `ω(1) when provided with a one-way function f : {0, 1} → {0, 1}, such that circuits of size poly(`) cannot invert f with probability ρ = 1/2 √ ` (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 ). *noga@cs.haifa.ac.il ronen@cs.haifa.ac.il nvarma@bu.edu

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)