## Speaker:

## Affiliation:

Rutgers University

Department of Computer Science

Hill Center, Room 418

New Brunswick, NJ

United States of America

## Webpage:

## Time:

## Venue:

## Organisers:

We will show that there is a family of n- variate polynomials of degree d = O(log^2 n), which can be computed by linear sized homogeneous depth-5 arithmetic circuits, where as any homogeneous depth-4 circuit computing it must have size at least n^{Omega(sqrt d)}.

This shows that for this range of parameters, the upper bounds for depth reductions to homogeneous depth-4 circuits obtained by Agrawal-Vinay, Koiran and Tavenas are tight up to constants in the exponent; even for very simple circuits like homogeneous depth-5 arithmetic circuits. Prior to this work, it was known that the depth reduction results are tight up to constants in the exponent, for algebraic branching programs (based on a joint work with Ramprasad Saptharishi).