Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Manindra Agrawal:

TR20-098 | 4th July 2020
Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

Impossibility of Derandomizing the Isolation Lemma for all Families

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

TR18-035 | 21st February 2018
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Bootstrapping variables in algebraic circuits

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>

ISSN 1433-8092 | Imprint