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