All reports by Author Ankit Gupta:

__
TR14-130
| 17th October 2014
__

Ankit Gupta#### Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

Revisions: 1

__
TR13-026
| 11th February 2013
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### Arithmetic circuits: A chasm at depth three

Revisions: 1

__
TR12-098
| 3rd August 2012
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

Revisions: 3

__
TR12-033
| 5th April 2012
__

Ankit Gupta, Neeraj Kayal, Youming Qiao#### Random Arithmetic Formulas can be Reconstructed Efficiently

__
TR11-153
| 13th November 2011
__

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam#### Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

Ankit Gupta

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

Ankit Gupta, Neeraj Kayal, Youming Qiao

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>

Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>