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

Different areas of mathematics, and theoretical computer science, freely borrow tools and ideas from each other and these interactions, like barters, can make both parties richer. In fact it's even better than barter: the objects being ideas, you don't have to actually give them up in an exchange. And so it is no surprise that … Continue reading From Discrepancy to Privacy, and back

I have been interested in fairness recently, both fairness in classification and the more traditional setting of fairness in resource allocation. Defining fairness is a tricky thing. Consider for example a resource to be divided between three people with equal claims for ownership. What is the fair division? It sounds natural that equal distribution of the … Continue reading Advanced Studies in Estate Management: He Who Was Married to Three Women

I love the ambitious spirit of our field. I embrace the view of Theory of Computation as a Lens on the Sciences. Avi Wigderson, a certified TOC-megalomaniac (used as a term of endearment), has been promoting this view for a while now and been making the point that fundamental notions such as Randomness, Entropy, Cryptography, … Continue reading Megalomania, Evolution without Sex, Drugs and Boolean Functions