Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.01708 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909303294656512 |
|---|---|
| author | Ron-Zewi, Noga Shaltiel, Ronen Varma, Nithin |
| author_facet | Ron-Zewi, Noga Shaltiel, Ronen Varma, Nithin |
| contents | A binary code Enc$:\{0,1\}^k \to \{0,1\}^n$ is $(0.5-ε,L)$-list decodable if for all $w \in \{0,1\}^n$, the set List$(w)$ of all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between Enc$(m)$ and $w$ is at most $0.5 -ε$, has size at most $L$. Informally, a $q$-query local list-decoder for Enc is a randomized procedure Dec$:[k]\times [L] \to \{0,1\}$ that when given oracle access to a string $w$, makes at most $q$ oracle calls, and for every message $m \in \text{List}(w)$, with high probability, there exists $j \in [L]$ such that for every $i \in [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 \ge 2^{k}$):
1. For $ε\geq 1/k^ν$ for some universal constant $0< ν< 1$, we prove a lower bound of $q=Ω(\frac{\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(\frac{\log(1/δ)}{ε^2})$ 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 \le 2^{k^γ}$ for some universal constant $0<γ<1$, 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).
2. For smaller $ε$, we prove a lower bound of roughly $q = Ω(\frac{1}{\sqrtε})$. To the best of our knowledge, this is the first lower bound on the number of queries of local list-decoders that gives $q \ge k$ for small $ε$.
We also prove black-box limitations for improving some of the parameters of the Goldreich-Levin hard-core predicate construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01708 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists) Ron-Zewi, Noga Shaltiel, Ronen Varma, Nithin Computational Complexity A binary code Enc$:\{0,1\}^k \to \{0,1\}^n$ is $(0.5-ε,L)$-list decodable if for all $w \in \{0,1\}^n$, the set List$(w)$ of all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between Enc$(m)$ and $w$ is at most $0.5 -ε$, has size at most $L$. Informally, a $q$-query local list-decoder for Enc is a randomized procedure Dec$:[k]\times [L] \to \{0,1\}$ that when given oracle access to a string $w$, makes at most $q$ oracle calls, and for every message $m \in \text{List}(w)$, with high probability, there exists $j \in [L]$ such that for every $i \in [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 \ge 2^{k}$): 1. For $ε\geq 1/k^ν$ for some universal constant $0< ν< 1$, we prove a lower bound of $q=Ω(\frac{\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(\frac{\log(1/δ)}{ε^2})$ 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 \le 2^{k^γ}$ for some universal constant $0<γ<1$, 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). 2. For smaller $ε$, we prove a lower bound of roughly $q = Ω(\frac{1}{\sqrtε})$. To the best of our knowledge, this is the first lower bound on the number of queries of local list-decoders that gives $q \ge k$ for small $ε$. We also prove black-box limitations for improving some of the parameters of the Goldreich-Levin hard-core predicate construction. |
| title | Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists) |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2409.01708 |