The Library
Algorithms and lower bounds for comparator circuits from shrinkage
Tools
Cavalar, Bruno P. and Lu, Zhenjian (2023) Algorithms and lower bounds for comparator circuits from shrinkage. Algorithmica, 85 . pp. 2131-2155. doi:10.1007/s00453-022-01091-y ISSN 0178-4617.
|
PDF
s00453-022-01091-y.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (420Kb) | Preview |
Official URL: http://doi.org/10.1007/s00453-022-01091-y
Abstract
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⩾logn, there exists a polynomial-time computable function fk on n bits such that, for every comparator circuit C with at most n1.5/O(k⋅logn−−−−√) gates, we have
Prx∈{0,1}n[C(x)=fk(x)]⩽12+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 n1.5/O(k⋅logn−−−−√) gates, in time 2n−k⋅poly(n) , for any k⩽n/4 . The running time is non-trivial (i.e., 2n/nω(1) ) when k=ω(logn) .
Pseudorandom Generators and MCSP Lower Bounds There is a pseudorandom generator of seed length s2/3+o(1) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n1.5−o(1)
lower bound for MCSP against comparator circuits.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Algorithmica | ||||||||
Publisher: | Springer Verlag | ||||||||
ISSN: | 0178-4617 | ||||||||
Official Date: | July 2023 | ||||||||
Dates: |
|
||||||||
Volume: | 85 | ||||||||
Page Range: | pp. 2131-2155 | ||||||||
DOI: | 10.1007/s00453-022-01091-y | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 3 March 2023 | ||||||||
Date of first compliant Open Access: | 3 March 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year