All reports by Author Pravesh Kothari:

__
TR23-162
| 1st November 2023
__

Pravesh Kothari, Peter Manohar#### An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

__
TR23-098
| 5th July 2023
__

Andrej Bogdanov, Pravesh Kothari, Alon Rosen#### Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

__
TR22-101
| 15th July 2022
__

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar#### A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

Revisions: 1

Pravesh Kothari, Peter Manohar

We prove that the blocklength $n$ of a linear $3$-query locally correctable code (LCC) $\mathcal{L} \colon \mathbb{F}^k \to \mathbb{F}^n$ with distance $\delta$ must be at least $n \geq 2^{\Omega\left(\left(\frac{\delta^2 k}{(|\mathbb{F}|-1)^2}\right)^{1/8}\right)}$. In particular, the blocklength of a linear $3$-query LCC with constant distance over any small field grows exponentially with $k$. ... more >>>

Andrej Bogdanov, Pravesh Kothari, Alon Rosen

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x = C(b)$ on at most $q$ coordinates. Existing constructions of $2$-LDCs achieve $n = ... more >>>