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.