Parameterized Parallel Computing and First-Order Logic

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

Jörg Flum, Yijia Chen

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)

Cites Work

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

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