| Title | : | Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction |
| Speaker | : | Purnata Ghosal (IIT Madras) |
| Details | : | Tue, Jul 18, 2017 4:00 PM, @ Turing Hall |
| Abstract | : | Abstract. We initiate the study of polynomials parameterized by degree
by arithmetic circuits of small syntactic degree. We define the notion of
fixed parameter tractability and show that there are families of polynomials
of degree $k$ that cannot be cannot be computed by
homogeneous depth four $Sigma Pi^{sqrt{k}} Sigma Pi^{sqrt{k}}$ circuits.
Our result implies that there is no parameterized depth reduction for circuits
of size $f (k)poly(n)$ such that the resulting depth four circuit is homogeneous.
We show that testing identity of depth three circuits with syntactic degree $k$ is fixed parameter tractable with $k$ as the parameter. Our algorithm involves an application of the hitting set generator given by Shpilka and Volkovich [APPROX-RANDOM 2009]. Further, we show that our techniques do not generalize to higher depth circuits by proving certain rank-preserving properties of the generator by Shpilka and Volkovich. This is based on a joint work with Om Prakash and Raghavendra Rao. The work will be presented at COCOON 2017 |