Some lower bounds in parameterized \(\mathrm{AC}^{0}\)

DOI10.1016/j.ic.2019.03.008zbMath1423.68196OpenAlexW2926972612MaRDI QIDQ2417855

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

halting problemclique problemcolor-coding techniqueparameterized \(\mathrm{AC}^{0}\)

Mathematics Subject Classification ID

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

Related Items

Parameterized Parallel Computing and First-Order Logic, Unnamed Item

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• First-order definability on finite structures
• Expected complexity of graph partitioning problems
• Describing parameterized complexity classes
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parametrized complexity theory.
• Semigroups, Presburger formulas, and languages
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Linear FPT reductions and computational lower bounds
• Large Cliques Elude the Metropolis Process
• Deciding First-Order Properties of Nowhere Dense Graphs
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• Database Theory - ICDT 2005
• From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item