Some Lower Bounds In Parameterized Ac(0)

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical AC(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 lower bound mentioned first we prove a strong AC(0) version of the planted clique conjecture: AC(0)-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size <= n(xi) (where 0 <= xi < 1). (C) 2019 Elsevier Inc. All rights reserved.