Algorithms and Lower Bounds for Comparator Circuits from Shrinkage
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\'al and Robere (ITCS 2020), who established …