Parameterized Analogues of Probabilistic Computation

Abstract

We study structural aspects of randomized parameterized computation. We introduce a new class $\mathsf{W}[\mathsf{P}]$-$\mathsf{PFPT}$ as a natural parameterized analogue of $\mathsf{PP}$. Our definition uses the machine based characterization of the parameterized complexity class $\mathsf{W}[\mathsf{P}]$ obtained by Chen et.al [TCS 2005]. We translate most of the structural properties and characterizations of the class $\mathsf{PP}$ to the new class $W[P]$-$\mathsf{PFPT}$. We study a parameterization of the polynomial identity testing problem based on the degree of the polynomial computed by the arithmetic circuit. We obtain a parameterized analogue of the well known Schwartz-Zippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79]. Additionally, we introduce a parameterized variant of permanent, and prove its $\#W[1]$ completeness.

Submitted to a conference