Talks
Fall 2018

Recent Structure Lemmas for Depth-two Threshold Circuits
Thursday, September 13th, 2018, 3:00 pm–3:30 pm
Event:
Speaker:
Lijie Chen (MIT)
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.
Attachment | Size |
---|---|
![]() | 502.11 KB |