文章基本信息

标题：Some Lower Bounds in Parameterized AC^0
本地全文：下载
作者：Yijia Chen ; J{\"o}rg Flum
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：58
页码：27:1-27:14
DOI：10.4230/LIPIcs.MFCS.2016.27
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 first lower bound, 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).
关键词：parameterized AC^0; lower bound; clique; halting problem