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 center dot Average-case Lower Bounds For every k = k(n) with k >= log n, there exists a polynomial-time computable function fk on n bits such that, for every comparator circuit C with at most n(1.5)/O (k center dot root log n) gates, we have Pr (x is an element of{0,1}n) [C(x) = fk (x)] <= 1/2 + 1/2(Omega(k)). This average-case lower bound matches the worst-case lower bound of Gal and Robere by letting k = O(log n). center dot # 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 center dot root log n) gates, in time 2(n-k) center dot poly(n), for any k <= n/4. The running time is non-trivial (i.e., 2(n)/n(omega(1))) when k =omega(log n). center dot 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.

Automated summary

In this paper, the study of average-case complexity and circuit analysis algorithms for comparator circuits is initiated. By utilizing the technique of shrinkage under random restrictions, new results are obtained for this model. These results include average-case lower bounds for comparator circuits, SAT algorithms, and pseudorandom generators and MCSP lower bounds.