The Library
Algorithms and lower bounds for comparator circuits from shrinkage
Tools
Tools
Tools
Cavalar, Bruno P. and Lu, Zhenjian (2022) Algorithms and lower bounds for comparator circuits from shrinkage. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Berkeley, CA, USA, 31 Jan - 03 Feb 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 215 pp. 1-21. ISBN 9783959772174. doi:10.4230/LIPIcs.ITCS.2022.34 ISSN 1868-8969.
|
PDF
WRAP-Algorithms-and-lower-bounds-for-comparator-circuits-from-shrinkage-Cavalar-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (902Kb) | Preview |
Official URL: http://doi.org/10.4230/LIPIcs.ITCS.2022.34
Abstract
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 Ω((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 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}ⁿ} [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^{ω(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.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Comparator circuits, Computer algorithms, Computational complexity | |||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||
| Place of Publication: | Dagstuhl, Germany | |||||||||
| ISBN: | 9783959772174 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 25 January 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 215 | |||||||||
| Page Range: | pp. 1-21 | |||||||||
| Article Number: | 34 | |||||||||
| DOI: | 10.4230/LIPIcs.ITCS.2022.34 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 28 March 2022 | |||||||||
| Date of first compliant Open Access: | 29 March 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Berkeley, CA, USA | |||||||||
| Date(s) of Event: | 31 Jan - 03 Feb 2022 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
