In this video, I present a paper from FOCS'23 on proving lower bounds for dynamic graph problems. I mainly survey previous results and bounds for proving data structure lower bounds and argue why previous techniques fail to address graph problems. I then present our new lower bounds and discuss the barriers we overcome to prove them.
Негізгі бет Super-Logarithmic Lower Bounds for Dynamic Graph Problems
Пікірлер