Parameterized analogues of probabilistic computation

DOI10.1007/978-3-319-14974-5_18MaRDI QIDQ5174962zbMATH OpenOpenAlexFDO

Authors Ankit Chauhan, B. V. Raghavendra Rao

Publication date 19 February 2015

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.7790

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parameterized complexity, tractability and kernelization (68Q27) Randomized algorithms (68W20)

Abstract: We study structural aspects of randomized parameterized computation. We introduce a new class $sfW[P]$-$sfPFPT$ as a natural parameterized analogue of $sfPP$. Our definition uses the machine based characterization of the parameterized complexity class $sfW[P]$ obtained by Chen et.al [TCS 2005]. We translate most of the structural properties and characterizations of the class $sfPP$ to the new class $W[P]$-$sfPFPT$. 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 $$ completeness.

Recommendations

• Parameterized Derandomization
• Parameterized random complexity
• Randomized Approximations of Parameterized Counting Problems
• Probabilistic parameterized polynomial time
• On parameterized counting

Cited in

(10)

• Probabilistic Ianov's schemes
• Parameterized random complexity
• Probabilistic parameterized polynomial time
• A note on parameterized polynomial identity testing using hitting set generators
• Parameterized Derandomization
• Probabilistic Recursion Theory and Implicit Computational Complexity
• On proving parameterized size lower bounds for multilinear algebraic models
• Parameterised counting in logspace
• Parameterised counting in logspace
• The challenges of unbounded treewidth in parameterised subgraph counting problems

This page was built for publication: Parameterized analogues of probabilistic computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5174962)