Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DEPTH THREE CIRCUIT:
Reports tagged with Depth Three Circuit:
TR11-061 | 18th April 2011
Neeraj Kayal

Affine projections of polynomials

Revisions: 1

An m-variate polynomial f is said to be an affine projection of some n-variate polynomial g if there exists an n \times m matrix A and an n-dimensional vector b such that f(x) = g(A x + b). In other words, if f can be obtained by replacing each variable ... more >>>


TR14-089 | 16th July 2014
Neeraj Kayal, Chandan Saha

Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field \mathbb{F} of characteristic zero. We resolve this problem by proving a N^{\Omega(\frac{d}{\tau})} lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>




ISSN 1433-8092 | Imprint