New algorithms and lower bounds for circuits with linear threshold gates
Ryan Williams · 2014
Let ACC o THR be the class of constant-depth circuits comprised of AND, OR, and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a "midpoint" between ACC (where we know nontrivial lower bounds) and depth-two linear threshold circuits (where nontrivial lower bounds remain open).