Abstract
It is a notorious open problem to prove strong lower bounds for an explicit function against depth-three majority circuits (depth-three TC0), or against depth-two linear threshold circuits (with arbitrary weights). I plan to briefly describe the n^(1.5-o(1)) gate lower bound for an explicit function against depth-three TC0 circuits (with Daniel Kane in STOC'16), as well as a gate lower bound for a function in E^(NP) against ACC^0 composed with depth-two linear threshold circuits (with Josh Alman and Timothy Chan in FOCS'16; similar results were proved independently by Suguru Tamaki). The first lower bound uses random restrictions, while the second lower bound uses the polynomial method; both results are still the state-of-the-art.