Abstract

I will first give an overviewof dynamic algorithms and their connections to other fields. Then, I willpresent our recent progress on the question "is there a dynamic algorithmwith small worst-case update time" for the spanning forest problem, whichis among central problems in dynamic algorithms on graphs. Our resultguarantees an n^{o(1)} worst-case update time with high probability, where n isthe number of nodes. The best worst-case bounds prior to our work are (i) thelong-standing O(\sqrt{n}) bound of [Frederickson STOC'83, Eppstein, Galil,Italiano and Nissenzweig FOCS'92] (which is slightly improved by aO(\sqrt{\log(n)}) factor by [Kejlberg-Rasmussen, Kopelowitz, Pettie, ThorupESA'16]) and (ii) the polylogarithmic bound of [Kapron, King and MountjoySODA'13] which works under an oblivious adversary assumption (our result doesnot make such assumption).

The crucial techniques areabout expanders: 1) an algorithm for decomposing a graph into a collection ofexpanders in near-linear time,and 2) an algorithm for "repairing" theexpansion property of an expander after deleting some edges of it. Thesetechniques can be of independent interest. 

This talk is based on resultsby [Nanongkai, Saranurak and Wulff-Nilsen,FOCS'17],[Nanongkai and Saranurak,STOC'17] and [Wulff-Nilsen, STOC'17].

Time

1月17日（周四）14:00-15:00

Speaker

Thatchaphol Saranurak is aresearch assistant professor at Toyota Technological Institute at Chicago. Hecurrently works on two topics in theoretical computer science.

 i).Barriersin dynamic graph problems: some dynamic graph problems have resisted many attemptsto improve their running time for decades. He investigates those barriers andtry to either break them or prove a (conditional) lower bound explaining why itis hard to improve.

 ii).Optimalself-adjusting binary search tree algorithms: a famous 30-year-old conjecturecalled "dynamic optimality conjecture" states that splay tree is anoptimal binary search tree algorithm. By formulating related easier questions,solving them, and making connections to many related areas in combinatorics, heis trying to make progress in proving this conjecture.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号