Algorithms and Lower Bounds for Comparator Circuits from Shrinkage.

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 them, we show Average-case Lower Bounds For every k = k (n) with k ⩾ log n , there exists a polynomial-time computable function f k on n bits such that, for every comparator circuit C with at most n 1.5 / O k · log n gates, we have Pr x ∈ 0 , 1 n C (x) = f k (x) ⩽ 1 2 + 1 2 Ω (k) . This average-case lower bound matches the worst-case lower bound of Gál and Robere by letting k = O log n . # SAT Algorithms There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n 1.5 / O k · log n gates, in time 2 n - k · poly (n) , for any k ⩽ n / 4 . The running time is non-trivial (i.e., 2 n / n ω (1) ) when k = ω (log n) . Pseudorandom Generators and MCSP Lower Bounds There is a pseudorandom generator of seed length s 2 / 3 + o (1) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n 1.5 - o (1) lower bound for MCSP against comparator circuits. [ABSTRACT FROM AUTHOR]