Parameterized Parallel Computing and First-Order Logic

DOI10.1007/978-3-030-48006-6_5OpenAlexW3028074942MaRDI QIDQ5049039FDOQ5049039

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

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

Mathematics Subject Classification ID

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

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Parametrized complexity theory.
• On uniformity within \(NC^ 1\)
• Title not available (Why is that?)
• Color-coding
• Parity, circuits, and the polynomial-time hierarchy
• Title not available (Why is that?)
• A fixed-parameter tractable algorithm for matrix domination
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• On the space and circuit complexity of parameterized problems: classes and completeness
• Describing parameterized complexity classes
• A logic for constant-depth circuits
• Title not available (Why is that?)
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• Fast parallel fixed-parameter algorithms via color coding
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• On the descriptive complexity of color coding
• Tree-depth, quantifier elimination, and quantifier rank
• FO-Definability of Shrub-Depth

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)