Parameterized Parallel Computing and First-Order Logic

DOI10.1007/978-3-030-48006-6_5MaRDI QIDQ5049039zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

Publication date 9 November 2022

Published in Fields of Logic and Computation III (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-48006-6_5

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Recommendations

• Parameterized Complexity Classes under Logical Reductions
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• Parameterized complexity of fixed variable logics
• scientific article; zbMATH DE number 2086399
• Describing parameterized complexity classes

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A fixed-parameter tractable algorithm for matrix domination
• A logic for constant-depth circuits
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Color-coding
• Describing parameterized complexity classes
• Fast parallel fixed-parameter algorithms via color coding
• FO-Definability of Shrub-Depth
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• scientific article; zbMATH DE number 5485586 (Why is no real title available?)
• On the descriptive complexity of color coding
• 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
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• Tree-depth, quantifier elimination, and quantifier rank

Cited in

(1)

• On the parallel parameterized complexity of MaxSAT variants

This page was built for publication: Parameterized Parallel Computing and First-Order Logic

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