Theory Lunch Seminar

Wednesday, April 18, 2018 - 12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates Hillman Centers

Speaker:

JONAH SHERMAN, Ph.D. Student https://people.eecs.berkeley.edu/~jsherman/

Regularization is one of the most powerful tools in continuous optimization, yet existing approaches using strong-convexity fail for several important problems due to the infamous "l_infinity barrier". In this talk, we show strong-convexity may be relaxed to a weaker notion of "area-convexity", for which those barriers do not apply. Using area-convex regularization, we obtain a fast algorithm for approximately solving matrix inequality systems AX <= B over right-stochastic matrices X. By combining that algorithm with recent work on maximum-flow, we obtain a nearly-linear time approximation algorithm for maximum concurrent flow in undirected graphs.

Event Website:

https://www.cs.cmu.edu/thttp%3A//www.cs.cmu.edu/~theorylunch/abstractsHTML/April...

For More Information, Contact:

Keywords:

Seminar Series