All reports by Author Nithin Varma:

__
TR20-133
| 8th September 2020
__

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma#### Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)

__
TR18-195
| 18th November 2018
__

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma#### Erasures versus Errors in Local Decoding and Property Testing

Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma

A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.

A $q$-query local list-decoder is ...
more >>>

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>