Parameterized Analogues of Probabilistic Computation

Ankit Chauhan, B. V. Raghavendra Rao

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 defin…