Circuit lower bounds - In the end, we know so little...Speaker: Chi-Ning
Title: Circuit lower bounds - In the end, we know so little...
Date: 22 Oct 2021 11:30-13:00 EST
Location: SEC Level 3 NW Terrace
Abstract: Circuit is one of the fundamental computational objects in CS, however, we know so little about it. In this casual lunch talk, we are going to have a peek into the history of researcher’s efforts in understanding circuit complexity through the lens of circuit lower bounds. I’ll also talk about some approaches I have been trying in the past 4 years and why I think circuit lower bounds are difficult and what could be missing.