All reports by Author Nithin Varma:

__
TR20-190
| 29th November 2020
__

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma#### Erasure-Resilient Sublinear-Time Graph Algorithms

__
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

Revisions: 1

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected ... more >>>

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 >>>