Parameterized circuit complexity of model-checking on sparse structures

DOI10.1145/3209108.3209136zbMath1497.68319arXiv1805.03488OpenAlexW2799268901MaRDI QIDQ5145356

Michał Pilipczuk, Szymon Toruńczyk, Sebastian Siebertz

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.03488

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Model theory of finite structures (03C13) Networks and circuits as models of computation; circuit complexity (68Q06) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Bounding generalized coloring numbers of planar graphs using coin models ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits ⋮ On the Descriptive Complexity of Color Coding

This page was built for publication: Parameterized circuit complexity of model-checking on sparse structures