Tag Archives: Moses Charikar

The Inaugural Motwani Lecture

Posted on by
1

The Stanford theory group is starting a once-a-term distinguished lecture in computer science, in memory of Rajeev Motwani.

We were very happy that Moses Charikar agreed to deliver the inaugural lecture, which will take place tomorrow, Thursday, at 4:15pm, in the Mackenzie Room, on the third floor of the new Engineering Complex. Moses will talk about dimension reduction in L1.

If you are coming, please also join us at 3pm for wine and cheese at the second-floor library in the Gates building.

Parking is free everywhere after 4pm.

More about the goings on at Stanford: theory.stanford.edu

Max Cut-Gain and the Smallest Eigenvalue

Posted on by
3

In June, I wrote about my work on using spectral partitioning to approximate Max Cut.

I have now posted a revised paper with a couple new things.

One is an improved analysis due to Moses Charikar, of the algorithm described in the June paper. Moses shows that if one starts from a graph in which the optimum cuts a 1-\epsilon fraction of edges, then the algorithm cuts at least a 1-4\sqrt \epsilon + 8\epsilon fraction of edges (and also at least half of the edges). Cutting more than a 1-\frac 2 \pi \sqrt \epsilon + o_\epsilon(1) fraction of edges is Unique-Games-hard. Optimizing the fraction

\displaystyle \frac{ \max \{ \ \frac 12 \ , \ (1-4\sqrt \epsilon + 8\epsilon) \ \} }{1-\epsilon}

we see that the approximation ratio of the algorithm is always at least .531.

The second new result answers a question raised by an anonymous commenter in June: what about Max Cut Gain? Continue reading →

The Next Viral Videos

Posted on by
5

Back in August, Boaz Barak and Moses Charikar organized a two-day course on additive combinatorics for computer scientists in Princeton. Boaz and Avi Wigderson spoke on sum-product theorems and their applications, and I spoke on techniques in the proofs of Szemeredi’s theorem and their applications. As an Australian model might say, that’s interesting!

Videos of the talks are now online. The quality of the audio and video is quite good, you’ll have to decide for yourself on the quality of the lectures. The schedule of the event was grueling, and in my last two lectures (on Gowers uniformity and applications) I am not very lucid. In earlier lectures, however, I am merely sleep deprived — I can be seen falling asleep in front of the board a few times. Boaz’s and Avi’s lectures, however, are flawless.