Some lower bounds in parameterized AC^0

DOI10.1016/J.IC.2019.03.008MaRDI QIDQ2417855zbMATH OpenOpenAlexWikidataFDO

Authors Yijia Chen, Jörg Flum

Publication date 29 May 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2019.03.008

zbMATH Keywords

clique problemcolor-coding techniquehalting problemparameterized \(\mathrm{AC}^{0}\)

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• Strong computational lower bounds via parameterized complexity
• Linear FPT reductions and computational lower bounds
• On hardness of approximating the parameterized clique problem
• Tight lower bounds for certain parameterized NP-hard problems

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• Database Theory - ICDT 2005
• Describing parameterized complexity classes
• Expected complexity of graph partitioning problems
• Fast parallel fixed-parameter algorithms via color coding
• First-order definability on finite structures
• From almost optimal algorithms to logics for complexity classes via listings and a halting problem
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• scientific article; zbMATH DE number 4003533 (Why is no real title available?)
• scientific article; zbMATH DE number 5485586 (Why is no real title available?)
• Large Cliques Elude the Metropolis Process
• Linear FPT reductions and computational lower bounds
• On the space and circuit complexity of parameterized problems: classes and completeness
• On uniformity within \(NC^ 1\)
• Parametrized complexity theory.
• Parity, circuits, and the polynomial-time hierarchy
• Semigroups, Presburger formulas, and languages

Cited in

(7)

• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• The parameterized space complexity of model-checking bounded variable first-order logic
• Parameterized Parallel Computing and First-Order Logic
• A fixed-depth size-hierarchy theorem for AC ⁰ [⊕] via the coin problem
• A parameterized halting problem, _0 truth and the MRDP theorem
• Uniformity within parameterized circuit classes
• Strong computational lower bounds via parameterized complexity

This page was built for publication: Some lower bounds in parameterized \(\mathrm{AC}^{0}\)

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