Abstract

We give two new structure lemmas for Depth-Two Threshold Circuits (THR of THR circuits) and apply them to identify potential approaches for proving super-polynomial THR of THR circuit lower bounds. Exponential-size lower bounds for the related (but weaker) classes THR of MAJ and MAJ of MAJ are well-known. Our results show that if one can mine some satisfiability or CAPP algorithms from these known lower bounds, that would already imply long-sought lower bounds for THR of THR circuits.

Video Recording