Abstract
Comparator circuits are a natural circuit model for studying bounded fanout 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 Ω((n/log n)^{1.5}) lower bound on the size of comparator circuits computing an explicit function of n bits.
In this paper, we initiate the study of averagecase 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
 Averagecase Lower Bounds. For every k = k(n) with k ≥ log n, there exists a polynomialtime 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}ⁿ} [C(x) = f_k(x)] ≤ 1/2 + 1/{2^{Ω(k)}}.
This averagecase lower bound matches the worstcase 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^{nk} · poly(n), for any k ≤ n/4. The running time is nontrivial (i.e., 2ⁿ/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.5o(1)} lower bound for MCSP against comparator circuits.
BibTeX  Entry
@InProceedings{cavalar_et_al:LIPIcs.ITCS.2022.34,
author = {Cavalar, Bruno P. and Lu, Zhenjian},
title = {{Algorithms and Lower Bounds for Comparator Circuits from Shrinkage}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {34:134:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15630},
URN = {urn:nbn:de:0030drops156303},
doi = {10.4230/LIPIcs.ITCS.2022.34},
annote = {Keywords: comparator circuits, averagecase complexity, satisfiability algorithms, pseudorandom generators}
}
Keywords: 

comparator circuits, averagecase complexity, satisfiability algorithms, pseudorandom generators 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 