Fall 2018

Recent Structure Lemmas for Depth-two Threshold Circuits

Thursday, Sep. 13, 2018 3:00 pm3:30 pm

Add to Calendar


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.