All reports by Author A. Shankar:

__
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

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