期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite having been studied for nearly three decades, the first superlinear lower bound against comparator circuits was proved only recently by Gál and Robere (ITCS 2020), who established a ((nlogn)15) lower bound on the size of comparator circuits computing an explicit function of n bits. In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among our results, we show - Average-case Lower Bounds. For every k=k(n) with klogn, there exists a polynomial-time computable function fk on n bits such that, for every comparator circuit C with at most n15O(klogn) gates, we have Prx01nC(x)=fk(x)21+12(k) This average-case lower bound matches the worst-case lower bound of Gál and Robere by letting k=O(logn). - #SAT Algorithms. There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n15Oklogn gates, in time 2n−kpoly(n), for any kn4 . The running time is non-trivial when k=(logn). - Pseudorandom Generators and MCSP Lower Bounds. There is a pseudorandom generator of seed length s23+o(1) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n15−o(1) lower bound for MCSP against comparator circuits.
