tcs math – some mathematics of theoretical computer science

January 7, 2011

Reading for a rainy day

Filed under: Math, Reading — James Lee @ 4:16 am

Today it’s raining in both Seattle and Paris. Here are a few things I think are worth reading while the weather clears up.

  • Stop collecting coupons. Recently, Batson, Spielman, and Srivastava gave a beautiful sparsification result for graphs: Every graph has a linear-sized spectral sparsifier. Here is one statement of their result (taken from Srivastava’s thesis):

    Theorem [BSS]: For every \varepsilon > 0 and m,n \in \mathbb N, the following holds. For every x_1, x_2, \ldots, x_m \in \mathbb R^n, there are non-negative numbers s_1, s_2, \ldots, s_m of which at most O(n/\varepsilon^2) are non-zero, and such that for all y \in \mathbb R^n,

    \displaystyle (1-\varepsilon)^2 \sum_{i=1}^m \langle x_i, y \rangle^2 \leq \sum_{i=1}^m s_i \langle x_i,y\rangle^2 \leq (1+\varepsilon)^2 \sum_{i=1}^m \langle x_i, y\rangle^2.

    Assaf Naor has given a very nice account of some recent geometric applications of this idea. These involves breaking the n \log n “coupon collecting” barrier from a number of results which were previously based on random sampling. There is still an outstanding open problem left open here: Embedding n-dimensional subspaces of L_1 into \ell_1^{O(n)}.

  • Lecture notes that are lecture notes. Some people write lecture notes like they are preliminary book drafts. These lecture notes by Ryan O’Donnell for an undergraduate course on “Probability and Computing” are like transcribed lectures. They’re conversational, with philosophical asides–a great example of the style.

  • Metaphors in systolic geometry. Larry Guth and Nets Katz recently made awesome progress on the Erdos distance problem in the plane. On a different note, here is a great informal survey of Guth on Gromov’s systolic inequality (which itself answers the question—when would an isometric embedding into L_{\infty} ever be employed for the usefulness of the ambient space?!)

  • An important epsilon. Finally, there is the recent result of Gharan, Saberi, and Singh giving a 3/2 - \varepsilon approximation for the Traveling Salesman Problem in unweighted graphs. I haven’t gotten a chance to digest the paper yet. Here’s hoping someone else will write an overview of the key ideas.
About these ads


  1. I think you have a typo: y is in R^n not R^m

    [Thanks, I fixed it. -j]

    Comment by Dan Feldman — January 11, 2011 @ 8:03 pm

  2. Anbody know how to get the problem sets (homework problems) associated with the “Probability and Computing” course mentioned above?

    Comment by George — February 21, 2011 @ 3:57 pm

  3. Thanks for the reading tips. Typical rainy day stuff.

    Comment by Silver Coast — October 26, 2011 @ 9:03 am

  4. Hi, the lecture notes link to Ryan O’Donnell’s “Probability and Computing” course seems to be dead. It will be helpful if someone in possession of the notes is willing to share it. Thanks.

    Comment by Dolby — July 27, 2012 @ 4:54 am

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Create a free website or blog at


Get every new post delivered to your Inbox.

Join 78 other followers

%d bloggers like this: