Some lower bounds in parameterized AC^0

DOI10.4230/LIPICS.MFCS.2016.27MaRDI QIDQ4608586zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

Publication date 21 March 2018

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

zbMATH Keywords

cliquehalting problemlower boundparameterized \(\mathrm{AC}^0\)

Mathematics Subject Classification ID

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

Abstract: We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical ${mAC}^0$. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the first lower bound, we prove a strong ${mAC}^0$ version of the planted clique conjecture: ${mAC}^0$-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size $le{n}^{x}i$ (where $0lexi<1$).

Recommendations

• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• Parameterized proof complexity
• Strong computational lower bounds via parameterized complexity
• Linear FPT reductions and computational lower bounds
• On hardness of approximating the parameterized clique problem

Cited in

(9)

• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• Computing Hitting Set Kernels By AC^0-Circuits
• Computing kernels in parallel: lower and upper bounds
• Parameterised counting in logspace
• On the parallel parameterized complexity of MaxSAT variants
• Existential second-order logic over graphs: parameterized complexity
• Parameterised counting in logspace
• Strong computational lower bounds via parameterized complexity

This page was built for publication: Some lower bounds in parameterized \(\mathrm{AC}^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608586)