Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR19-128 | 24th September 2019 05:58

Lower Bounds for (Non-monotone) Comparator Circuits

TR19-128
Authors: Anna Gal, Robert Robere
Publication: 24th September 2019 05:59
Downloads: 1040
Keywords:

Abstract:

Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and Boolean formulas. In this paper we prove the first superlinear lower bounds in the general (non-monotone) version of this model for an explicitly defined function. More precisely, we prove that the \$n\$-bit Element Distinctness function requires \$\Omega( (n/ \log n)^{3/2})\$ size comparator circuits.

ISSN 1433-8092 | Imprint