![Meta-complexity_logo_hi-res](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Meta-complexity_hi-res.png.jpg?itok=oFqprXq1)
Abstract
In this talk, I will present a "derandomization-centric" perspective on Williams' algorithmic method. In particular, I will give outlines of alternative proofs of Murray and Williams' lower bound that nondeterministic quasi-polynomial time does not have polynomial-size ACC^0 circuits. I will also discuss new results from this perspective, including a lower bound showing that NEXP does not have sub-half-exponential-size ACC^0 circuits (improving the sub-third-exponential-size bound in Williams' previous work).