I love sports, at least watching it. I could be tempted to follow any competition in any sport (with the obvious exceptions of baseball, cricket and golf). Now that the London Olympic games are almost forgotten and the world cup a full year and a half away (576 days to be precise) I want to … Continue reading Tennis for the People

Due to the effects of Hurricane Sandy, the deadline for STOC 2013 has been extended to Monday, November 5, 5pm EST, see http://stoc.cs.yale.edu/stoc2013/ 

This is the season for academic job searches, and if you are looking for a postdoc in theoretical Computer Science, we hope you consider applying for a position at Microsoft Research. The various MSR labs are looking for postdocs in many scientific fields, including all areas of theoretical Computer Science. You can apply for postdoc … Continue reading Postdoc positions at MSR

The following message from Joan Feigenbaum describes some major changes in the new formatting requirements. While these changes may be controversial, it’s important to take note. --------------------- 1) Please read the Call for Papers carefully and pay special attention to length and formatting requirements, which have changed since last year: a) Submissions must be no … Continue reading Message from STOC 2013 PC Chair – Joan Feigenbaum

This post is about implementing cryptography with real objects—rods, chains, and locks—and it is going to be light on formulas and heavy on pictures. Fun! Many cryptographic schemes have real-world analogues, some less trivial than others. Digital signatures are the most obvious example, where the cryptographic scheme achieves pretty much the same task as traditional … Continue reading Cryptography in the Real World

Hiring season is upon us, and I promised myself last year to spread the following tip: when you are applying for a position, make sure that somebody relevant knows you are applying. Just submitting the application online may mean that it falls between the cracks (especially in places where the number of applicants is very … Continue reading A Quick Hiring Tip: Don’t Trust the Machine

In this post, I will present what I think is a simple(r) algorithm for estimating the $latex k>2$ frequency moment, or simply the $latex \ell_k$ norm of a vector, in the sketching/streaming model. In fact, the algorithm is just a weak embedding of $latex n$-dimensional $latex \ell_k$ into $latex \ell_\infty$ of dimension $latex m=O(n^{1-2/k}\log n)$ … Continue reading High frequency moments via max-stability

The 2012 MacArthur Fellows have recently been announced. Many congratulations to all the winners, including Dan Spielman and Maria Chudnovsky.

Let me start by saying that I have never read any blog posts, let alone written one, until today.  You are probably asking yourself, why am I blogging then? Well, the truth is that the only reason is that I couldn't resist Omer's charm when he asked me to join the blog. I decided to … Continue reading The Evolution of Proofs

The birthday paradox is most commonly presented as a thought experiment: How many people should be invited to a party that the odds of finding two persons sharing the same birthday be more than even? The answer is 23, which is surprisingly low and counter-intuitive. Other than the unexpectedly small numeric value, there is nothing … Continue reading ‘Tis the Season for C-Section