| Title | : | Parameterized Analogues of Probabilistic Computation |
| Speaker | : | Ankit Chauhan (IITM) |
| Details | : | Mon, 15 Jun, 2015 4:00 PM @ BBS 361 |
| Abstract: | : | We introduce the parameterized probabilistic class W[p]-PFPT to strengthen our understanding of parameterized counting complexity. Our definition uses the
machine based characterization of the parameterized complexity class W[p] obtained by Chen et.al. We establish the structural properties and
characterizations of W[p]-PFPT analogues to the class PP.
We study a parameterization of the polynomial identity testing problem based on the degree of the polynomial computed by an arithmetic circuit. We obtain a parameterized analogue of the well known DeMillo-Lipton-Schwartz-Zippel Lemma. Further, we study parameterizations for a number of problems on arithmetic circuits. To state a few : checking for existence of monomials, counting monomials, Hadamard product, which are parameterized over 1) degree of polynomial, 2) syntactic degree of arithmetic circuit and 3) degree of monomial. We show hardness as well as upper bounds for some special cases of these problems such as counting monomials when the circuit is monotone circuit. Additionally, we introduce a parameterized variant of permanent, and prove its #W[1] completeness. |
