文章基本信息

标题：Lower Bounds for (Non-Monotone) Comparator Circuits
本地全文：下载
作者：Anna G{'a}l ; Robert Robere
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-13
DOI：10.4230/LIPIcs.ITCS.2020.58
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Î©((n/ log n)^(3/2)) size comparator circuits.
关键词：comparator circuits; circuit complexity; Nechiporuk; lower bounds