[Colloquium] [Faculty] Theory Seminars at Computer Science

[Alexander Razborov]

... time is the same (3pm).

Sasha.

> On Jun 18, 2015, at 7:38 PM, Donna Brooms <donna at cs.uchicago.edu> wrote:
> 
> Combinatorics & Theoretical Computer Science Seminar
> 
> Note: Different Location and Time:
> 
> Ali Kemal Sinop
> UC Berkeley
> www.cs.cmu.edu/~asinop
> 
> Tuesday, June 23, 2015
> 6045 S. Kenwood
> TTIC - 530
> 
> Title: How to Round Subspaces: A New Spectral Clustering Algorithm
>  
> Abstract:
> Consider the problem of approximating a $k$-dimensional linear subspace with another {$k$-piecewise} constant subspace in spectral norm. This problem is at the heart of many spectral methods used in data clustering and graph partitioning.  Our main contribution is a new spectral clustering algorithm: It can recover a $k$-partition such that the subspace corresponding to the span of its indicator vectors is $O(\sqrt{opt})$ close to the original subspace in spectral norm, with $opt$ being the minimum possible. Moreover our algorithm does
> not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a $k$-partition closer than $o(k \cdot opt)$.
> We present two applications for our algorithm. First one finds a disjoint union of $k$-expanders which approximate a given graph in spectral norm. The second one is for approximating the $k$-partition whose clusters have expansion at most $\phi_k$ on graphs satisfying $\phi_k \le O(\lambda_{k+1})$ where $\lambda_{k+1}$ is the $(k+1)^{th}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $\phi_k \le O(\lambda_{k+1}/k)$.
>  
> Host: Prof. Madhur Tulsiani
>  
> (Refreshments will be served prior to the talk at 2:45 p.m. in TTIC – 526)
> _______________________________________________
> Colloquium mailing list  -  Colloquium at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
> _______________________________________________
> faculty mailing list  -  faculty at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/faculty
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150618/a7a2ed72/attachment.htm