License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2019.3
URN: urn:nbn:de:0030-drops-114648
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11464/
Go to the corresponding LIPIcs Volume Portal

Bläser, Markus ; Engels, Christian

Parameterized Valiant's Classes

pdf-format:
LIPIcs-IPEC-2019-3.pdf (0.5 MB)

Abstract

We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolean counting classes #FPT and #W[t], and define appropriate reductions and completeness notions. Our main contribution is the VW[1]-completeness proof of the parameterized clique family. This proof is far more complicated than in the Boolean world. It requires some new concepts like composition theorems for bounded exponential sums and Boolean-arithmetic formulas. In addition, we also look at two polynomials linked to the permanent with vastly different parameterized complexity.

BibTeX - Entry

@InProceedings{blser_et_al:LIPIcs:2019:11464,
  author =	{Markus Bl{\"a}ser and Christian Engels},
  title =	{{Parameterized Valiant's Classes}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Bart M. P. Jansen and Jan Arne Telle},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11464},
  URN =		{urn:nbn:de:0030-drops-114648},
  doi =		{10.4230/LIPIcs.IPEC.2019.3},
  annote =	{Keywords: Algebraic complexity theory, parameterized complexity theory, Valiant's classes}
}

Keywords: Algebraic complexity theory, parameterized complexity theory, Valiant's classes
Collection: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI