Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Comparator Circuits:
TR15-035 | 22nd February 2015
Sunil K S, Balagopal Komarath, Jayalal Sarma

Comparator Circuits over Finite Bounded Posets

Revisions: 1

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>>

TR16-064 | 19th April 2016
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Exponential Lower Bounds for Monotone Span Programs

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

TR16-188 | 21st November 2016
Toniann Pitassi, Robert Robere

Strongly Exponential Lower Bounds for Monotone Computation

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where $N$ is the number of variables of the ... more >>>

TR19-128 | 24th September 2019
Anna Gal, Robert Robere

Lower Bounds for (Non-monotone) Comparator Circuits

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 ... more >>>

TR21-035 | 13th March 2021
Robert Robere, Jeroen Zuiddam

Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

Revisions: 1

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ... more >>>

TR21-171 | 2nd December 2021
Bruno Pasqualotto Cavalar, Zhenjian Lu

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

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 ... more >>>

ISSN 1433-8092 | Imprint