Parameterized circuit complexity of model-checking on sparse structures

DOI10.1145/3209108.3209136zbMath1497.68319arXiv1805.03488MaRDI 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

68R10: Graph theory (including graph drawing) in computer science

68Q60: Specification and verification (program logics, model checking, etc.)

03C13: Model theory of finite structures

68Q06: Networks and circuits as models of computation; circuit complexity

68Q27: Parameterized complexity, tractability and kernelization