ÿþ<HTML> <HEAD> <TITLE>2012 Erd&#337;s Lectures in Discrete Mathematics and Theoretical&nbsp;Computer&nbsp;Science </TITLE> <script type="text/javascript"> function toggle(obj) { var obj=document.getElementById(obj); if (obj.style.display == "block") obj.style.display = "none"; else obj.style.display = "block"; } </script> </HEAD> <BODY BGCOLOR="#FFFFF0" TEXT="#000000" LINK="#003366" VLINK="#440088" ALINK="#FF0000"> <TABLE WIDTH=70% ALIGN="CENTER" BORDER=0" <TR> <TD WIDTH=40%> <A HREF="http://www.huji.ac.il/" TARGET="_blank" style="text-decoration: none"> The Hebrew University of Jerusalem</A><BR> <A HREF="http://www.ma.huji.ac.il" TARGET="_blank" style="text-decoration: none"> Einstein Institute of Mathematics</A> <TD WIDTH=20%> <A HREF="http://www.huji.ac.il/" style="text-decoration: none"> <IMG SRC="../gifs/HUJI_logos1_08.jpg" ALT="Hebrew University of Jerusalem" width=97 height=99 BORDER=0 hspace=10 vspace=10></A> <TD WIDTH=40%> <A HREF="http://www.huji.ac.il/" TARGET="_blank" style="text-decoration: none"> The Hebrew University of Jerusalem</A><BR> <A HREF="http://www.cse.huji.ac.il/" TARGET="_blank" style="text-decoration: none"> The Rachel and Selim Benin School of Computer Science & Engineering</A> <TR> <TH COLSPAN=3>Center for Theoretical Computer Science and Discrete Mathematics </TABLE><P> <CENTER> <font face="Times New Roman,Times" SIZE=+1> <A HREF="erdos.html" style="text-decoration: none"> Erd&#337;s Lectures in Discrete Mathematics and Theoretical&nbsp;Computer&nbsp;Science</A> </font></B> </CENTER> <HR><P> <CENTER> The Hebrew University Center for Theoretical Computer Science and Discrete Mathematics invites you to this year's Erd&#337;s&nbsp;Lecture&nbsp;in&nbsp;Discrete&nbsp;Mathematics&nbsp;and&nbsp; Theoretical&nbsp;Computer&nbsp;Science<P> <FONT SIZE=+2><B> <I>Prof. <A HREF="http://www.cs.stanford.edu/~trevisan" style="text-decoration: none" TARGET="_blank"> Luca Trevisan</A></I> &nbsp;&nbsp; (Stanford)</B> </FONT> </CENTER> <HR> <BLOCKQUOTE> <B>Lectures</B>: <!-- &nbsp;&nbsp;&nbsp;&nbsp; (<B><A HREF="erdos_10.pdf">Poster</A></B>) --> <OL> <LI><B>A higher-order Cheeger Inequality</B><BR> <I>Thursday, May 3rd</I> &nbsp;&nbsp; 4:00 pm &nbsp;&nbsp; Mathematics Building, Lecture Hall 2 &nbsp;&nbsp; Department Colloquium<BR> <a href="javascript: void(0);" onClick="toggle('a1')">Abstract</a> <div id="a1" style="display:none;"> A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero.<P> Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.<P> It has been conjectured that an analogous characterization holds for higher multiplicities, i.e., there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut.<P> In this lecture we describe joint work with James Lee and Shayan Oveis Gharan in which we resolve this conjecture. </div><P> <LI><B>Dimension-reduction and multi-way spectral partitioning</B><BR> <I>Monday, May 7th</I>, &nbsp;&nbsp; 11:00 am &nbsp;&nbsp; Ross Building, Room 201<BR> <a href="javascript: void(0);" onClick="toggle('a2')">Abstract</a> <div id="a2" style="display:none;"> In the previous lecture we outlined a proof that if the normalized Laplacian matrix of a graph has k eigenvalues smaller than epsilon, then there are k disjoint subsets of vertices each of expansion at most O(k^2 * epsilon^1/2 ). Via dimension-reduction techniques, we show that it is also possible to find 0.99*k disjoint subsets of vertices, each of expansion at most O( (epsilon * log k)^1/2 ), which is a tight result.<P> This lecture describes joint work with James Lee and Shayan Oveis Gharan. </div><P> <LI><B>Approximating the expansion profile</B><BR> <I>Wednesday, May 9th</I> &nbsp;&nbsp; 10:30 am &nbsp;&nbsp; Ross Building, Room 201<BR> <a href="javascript: void(0);" onClick="toggle('a3')">Abstract</a> <div id="a3" style="display:none;"> In the "expansion profile" problem and the "small-set expander" problem we are interested in the following question: given a graph and a parameter k, find the subset of k or fewer vertices with the smallest expansion.<P> Using the "evolving sets" algorithm of Anderson and Peres, we provide the following approximation guarantee: if there is a set of size at most k and expansion epsilon, we can find a set of size at most k*n^(1/c) and expansion at most O( (c * epsilon)^(1/2) ). Furthermore, the running time of the algorithm is nearly-linear in the size of the output set. This is the first algorithm for the expansion profile problem that does not lose factors of (log n)^(Omega(1)) in the expansion.<P> This lecture describes joint work with Shayan Oveis Gharan. </div><P> </OL> </BLOCKQUOTE> <HR noshade> <font size=-1><B>Comments to</B>: Naavah Levin, email: <I>naavah at math.huji.ac.il</I><BR> <B>Design, construction &amp; editing</B>: Naavah Levin<BR> <B>Last updated</B>: April 30th, 2012</font> </BODY> </HTML>