REVIEW 1 cited by
Parameterized Valiant's Classes
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Parameterized Valiant's Classes
read the original 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.
Forward citations
Cited by 1 Pith paper
-
Kronecker products and iterated matrix multiplication
Kronecker products applied to iterated matrix multiplication define the hypercomputant, a VNP-complete and VW[1]-complete polynomial whose hardness follows from equivariance, with extensions to semirings, tensor algeb...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.