Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

Bruno P. Cavalar, Zhenjian Lu

Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite…