Blackbox Polynomial Identity Testing for Depth 3 Circuits

Neeraj Kayal and Shubhangi Saraf

2009

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). Our main technical result is a structural theorem for depth three circuits with bounded top fanin that compute the zero polynomial. In particular we show that if a circuit C with real coefficients is simple, minimal and computes the zero polynomial, then the rank of C can be upper bounded by a function only of the top fanin. This proves a weak form of a conjecture of Dvir and Shpilka (STOC 2005) on the structure of identically zero depth three arithmetic circuits.

Publication type | Inproceedings |

Published in | Foundations of Computer Science (FOCS) |

URL | http://eccc.hpi-web.de/report/2009/032/ |

Publisher | IEEE IEEE |

- Complexity of Ring Morphism Problems
- On the Sum of Square Roots of Polynomials and related problems
- Super-polynomial lower bounds for depth four homogeneous arithmetic formulas

> Publications > Blackbox Polynomial Identity Testing for Depth 3 Circuits