All reports by Author A. Shankar:

__
TR23-185
| 27th November 2023
__

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes

Revisions: 3

__
TR22-182
| 16th December 2022
__

Prahladh Harsha, Tulasi mohan Molli, A. Shankar#### Criticality of AC0-Formulae

Revisions: 1

__
TR21-163
| 19th November 2021
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Algorithmizing the Multiplicity Schwartz-Zippel Lemma

Revisions: 1

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they ... more >>>

Prahladh Harsha, Tulasi mohan Molli, A. Shankar

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function $f : \{0, 1\}^n\to \{0, 1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$,

\[Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.\]

.

Håstad’s celebrated switching lemma ...
more >>>

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found nu- merous applications in both math and computer ... more >>>