Some Lower Bounds in Parameterized AC^0.

DOI10.4230/LIPIcs.MFCS.2016.27zbMath1398.68190arXiv1606.08014OpenAlexW2963579754MaRDI QIDQ4608586

Jörg Flum, Yijia Chen

Publication date: 21 March 2018

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

zbMATH Keywords

lower boundcliquehalting problemparameterized \(\mathrm{AC}^0\)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Computing Hitting Set Kernels By AC^0-Circuits ⋮ Parameterised counting in logspace ⋮ Unnamed Item ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits

This page was built for publication: Some Lower Bounds in Parameterized AC^0.