Some lower bounds in parameterized \rm AC⁰

2016/06/26 by Yijia Chen, Chen, Yijia, Joerg Flum +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Clique #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Conjecture #Descriptive complexity theory #Discrete mathematics #FOS: Computer and information sciences #Graph #Mathematics #Parameterized complexity #Time complexity #Upper and lower bounds #cs.CC #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1606.08014

arxiv created 2016/06/26 · openalex publication_date 2016/06/26 · arxiv updated 2016/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical \rm AC⁰. 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 \rm AC⁰ version of the planted clique conjecture: \rm AC⁰-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size ≤ n^ξ (where 0 ≤ ξ< 1).

Citations

• Parameterized Complexity Theory
• Large Cliques Elude the Metropolis Process
• Parity, circuits, and the polynomial-time hierarchy

Related

• On Lower Bounds of Approximating Parameterized k-Clique
• Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
• Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
• A parameterized halting problem, Δ₀ truth and the MRDP theorem
• Hardness of clique approximation for monotone circuits