CORE Seminar: Jon Kel­ner

Flow and cut prob­lems on graphs are among the most fun­da­men­tal and exten­sively stud­ied prob­lems in Oper­a­tions Research and Opti­miza­tion, play­ing a foun­da­tional role in both the the­ory and prac­tice of algo­rithm design. While the clas­si­cal algo­rithms for these prob­lems were largely based on com­bi­na­to­r­ial approaches, the past sev­eral years have wit­nessed the emer­gence of a pow­er­ful col­lec­tion of new tech­niques based on geom­e­try, spec­tral graph the­ory, com­pu­ta­tional lin­ear alge­bra, ran­dom­iza­tion, and iter­a­tive meth­ods from con­tin­u­ous opti­miza­tion. These numer­i­cal tech­niques have allowed researchers to pro­vide bet­ter prov­able algo­rithms for a wide range of graph prob­lems, in some cases break­ing algo­rith­mic bar­ri­ers that had stood for sev­eral decades.

The rela­tion­ship between graph the­ory and numer­i­cal analy­sis has proven fruit­ful in the other direc­tion as well. In addi­tion to pro­vid­ing numer­i­cal tech­niques for graph algo­rithms, it has given rise to new com­bi­na­to­r­ial tech­niques for com­pu­ta­tional lin­ear alge­bra. In par­tic­u­lar, it has led to fast algo­rithms for Lapla­cian lin­ear sys­tems, which have broad appli­ca­tions in numer­i­cal sci­en­tific com­put­ing, machine learn­ing, oper­a­tions research, com­puter vision, and net­work analy­sis, among others.

In this talk, I dis­cuss some of the recur­ring themes that arise in this con­flu­ence of fields. I will apply these to sketch algo­rithms that run in close to lin­ear time for two basic algo­rith­mic prob­lems: solv­ing Lapla­cian lin­ear sys­tems and find­ing approx­i­mately max­i­mum flows on undi­rected graphs.

The talk will be based on joint work with Yin Tat Lee, Aaron Sid­ford, Lorenzo Orec­chia, and Zeyuan Zhu.