[Colloquium] THEORY SEMINAR: Yury Makarychev on January 18

[Donna Brooms]

> 
> 
> DEPARTMENT OF COMPUTER SCIENCE
> 
> UNIVERSITY OF CHICAGO
> 
> Date: Tuesday, January 18, 2011
> Time: 3:00 p.m.
> Place: Ryerson 251, 1100 E. 58th Street
> 
> ----------------------------------------------
> 
> Speaker:		Yury Makarychev
> 
> From:		TTI-Chicago
> 
> Web page:	http://ttic.uchicago.edu/~yury/
> 
> Title: 		Metric Extension Operators, Vertex Sparsifiers and Lipschitz
> Extendability
> 
> Abstract:  	We study vertex cut and flow sparsifiers that were recently introduced
> by Moitra, and Leighton and Moitra. We improve
> and generalize their results. We give a new polynomial-time algorithm
> for constructing O(log k / log log k) cut and flow
> sparsifiers, matching the best existential upper bound on the quality of
> a sparsifier, and improving the previous algorithmic
> upper bound of O(log^2 k / log log k). We show that flow sparsifiers can
> be obtained from linear operators approximating
> minimum metric extensions. We introduce the notion of (linear) metric
> extension operators, prove that they exist, and give
> an exact polynomial-time algorithm for finding optimal operators.
> 
> We then establish a direct connection between flow and cut sparsifiers
> and Lipschitz extendability of maps in Banach spaces,
> a notion studied in functional analysis since 1930s. Using this
> connection, we prove a lower bound of Omega(sqrt{log k/log log k}) for
> flow sparsifiers and a lower bound of Omega(sqrt{log k}/log log k) for
> cut sparsifiers. We show that if a certain open question posed
> by Ball in 1992 has a positive answer, then there exist \tilde
> O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut
> sparsifiers better than \tilde Omega(sqrt{log k}) would imply a negative
> answer to this question.
> 
> Joint work with Konstantin Makarychev
> 
> Refreshments will be served prior to the talk at 2:30 in Ryerson 255.
> _______________________________________________
> Colloquium mailing list  -  Colloquium at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
> _______________________________________________
> staff mailing list  -  staff at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/staff
>