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

In this post I wanted to share some background and thoughts about leakage-resilient cryptography, which has recently been the focus of a rich body of research. Before saying anything more, I do want to emphasize that this is not meant to be a survey – just a collection of thoughts and observations about recent work … Continue reading On Leakage-Resilient Cryptography

Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the $latex {P}&fg=000000$ vs $latex {NP}&fg=000000$ problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could … Continue reading Truth vs Proof: The Unique Games Conjecture and Feige’s Hypothesis

Having your assumptions and beliefs challenged by a group of seasoned law enforcement professionals and subject matter experts can be a rather disturbing experience. It is exactly what happened to me this week during the workshop on the role of technology in combating human trafficking, organized by Rane Johnson-Stempson, danah boyd, and the good folks … Continue reading Inconvenient Truth