Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR22-182 | 16th December 2022
Prahladh Harsha, Tulasi mohan Molli, A. Shankar

Criticality of AC0-Formulae

Revisions: 1

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

TR21-163 | 19th November 2021
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar

Algorithmizing the Multiplicity Schwartz-Zippel Lemma

Revisions: 1

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

ISSN 1433-8092 | Imprint