New algorithms and lower bounds for circuits with linear threshold gates

Ryan Williams

Let $ACC\circ THR$ be the class of constant-depth circuits comprised of AND, OR, and MOD$m$ gates (for some constant $m>1$), with a bottom layer of gates computing arbitrary lin…