| Title | : | On Identity Testing of Constant-Depth circuits parameterized by degree |
| Speaker | : | Purnata Ghosal (IITM) |
| Details | : | Tue, 4 Dec, 2018 4:00 PM @ Turing Hall |
| Abstract: | : | We initiate the study of polynomials parameterized by degree by
arithmetic circuits of small syntactic degree. We show that the
polynomial hitting set generator defined by Shpilka and
Volkovich [APPROX-RANDOM 2009] has the following property:
If an n-variate polynomial f has a partition of variables such that the partial derivative matrix [Raz, 2009] has large rank then its image under the Shpilka-Volkovich generator too has large rank even under a random partition. Our result implies that Shpilka-Volkovich generator will not be useful in obtaining efficient parameterized algorithms for the arithmetic circuit identity testing problem, with depth greater than three and degree of the polynomial as the parameter |
