Graph ComplexitySpeaker: Chi-Ning
Title: Graph Complexity
Date: 05 Nov 2018 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Abstract: Graph complexity is a program for proving circuit lower bound with a long history initiated by Pudlák, Rödl,and Savickÿ. The general idea is reducing the task of proving circuit lower bounds to showing the lower bounds for certain graph properties. It is not clear whether this approach makes the lower bound problem even harder or makes our lives better. On the bright side, the strongly exponential lower bound for depth-3 AC0 circuits with bottom XOR gates had been proved using graph complexity by Jukna. On the other hand, several conjectures in graph complexity that have great consequences in circuit lower bound remain widely open.
In this talk, I’m going to briefly survey some classic connections between graph complexity and circuit complexity. If time allows, I’ll also discuss some potential approach in proving new graph complexity lower bounds. See attached notes for preview.
- Chi-Ning’s notes: link.