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

You are heading to Paris for the first time. You finally get there and it is time for dinner, you need to pick a restaurant. Of course you would like to avoid  Tourists-Traps. Traditionally, people were relying on rule of thumb, and if they were lucky and knew someone that has some useful information, they … Continue reading Community brain

Hastad's Switching Lemma is one of the gems of computational complexity. The switching lemma analyzes the effect of random restrictions on $latex AC^0$ circuits, which are constant depth circuits with AND, OR and NOT gates of unbounded fanin. It says that such restrictions tends to simplify  $latex AC^0$ circuits in surprising ways. An immediate consequence of the switching lemma is strong … Continue reading The Switching Lemma

Tim Gowers reports on a new set of open access math journals. There will be a Forum of Mathematics:Pi that is supposed to be a generalist math journal, and Forum of Mathematics:Sigma that would have "clusters" for different areas. It will be paid for by Cambridge University Press for the first three years, and will then … Continue reading Interesting new development in Math publishing

In memory of Mihai Pătraşcu. Continuing the spirit of the previous post, in this post I will describe a specific technique for proving lower bounds for (static) data structures, when the space is (near) linear. This technique was introduced in the paper by Mihai and Mikkel Thorup, called "HIGHER lower Bounds for Near-Neighbor and  F … Continue reading Higher Lower Bounds: Just Ask for More!

In memory of Mihai  Pătraşcu Written by Rasmus Pagh, Rina Panigrahy, Kunal Talwar and Udi Wieder Reductions are arguably at the heart of complexity theory. They show that one problem is at least as hard as another. Finding reductions often requires creativity and considerable technical skill; some reductions seem as if they were pulled from thin air. The most difficult … Continue reading The Art of Reductions

Tim Roughgarden sent me the following email. I found this idea so refreshing that I thought I should share more widely. Well done PC! -------------------------------------------------------------------------------- PC meetings are typically all work and no play.  But the FOCS '12 PC, in an act of rebellion, has decided to spend a day disucssing their own results, before … Continue reading “Just a Spoonful of Sugar …”