All reports by Author Anamay Tengse:

__
TR20-187
| 13th December 2020
__

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### If VNP is hard, then so are equations for it

__
TR20-063
| 29th April 2020
__

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### On the Existence of Algebraically Natural Proofs

Revisions: 1

__
TR18-132
| 17th July 2018
__

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse#### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

Revisions: 2

__
TR17-135
| 10th September 2017
__

Ramprasad Saptharishi, Anamay Tengse#### Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees

Revisions: 1

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP *does not* have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size.

In a ... more >>>

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:

* For every family {f_n} of polynomials in VP, where f_n is an n ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... more >>>

Ramprasad Saptharishi, Anamay Tengse

We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) and give the following constructions:

• An explicit hitting set of quasipolynomial size for ...
more >>>