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 …”

Is it “safe” to release aggregate statistics from a database of sensitive information on individuals? Evidence suggests that even seemingly innocuous statistical releases can fatally compromise an individual’s privacy, especially in the presence of auxiliary information about the individual (see this paper by Homer et al. for a recent example). How might we then get … Continue reading Privacy-Preserving Data Analysis and Computational Learning: A Match made in Heaven

Part II. For Part I see here. Having largely reproduced the main results of the Lenstra et al. paper, the next research question became identifying the root cause or causes of this vulnerability. There was no shortage of explanations put forward shortly after the paper was released, and we were able to critically examine some of … Continue reading Factoring RSA Moduli. Part II.

In my first post on this blog I would like to expand its range of topics to applied cryptography and share some interesting new findings that so far have not been reported anywhere else except a Eurocrypt'12 rump session talk. On Valentine's Day earlier this year, the paper with a somewhat enigmatic title ``Ron was … Continue reading Factoring RSA Moduli. Part I.

The first question we'd like to answer is this: which is the monotone, balanced, transitive Boolean function which is least sensitive to bit-flips? We know that Majority is the worst possible with $latex NS( Maj) = \Theta(1/\sqrt{n})$. The new champion turns out to be the Tribes function first studied by Ben-Or and Linial. $latex Tribes_{s,w}$ … Continue reading When did Majority become the stablest? (Part 2)

The fireworks happening over at Ryan O'Donnell's blog reminded me of something that always puzzles me: Is Majority the Stablest? Or the Unstablest? Consider the class of all monotone, balanced Boolean functions $latex f:\{-1,1\}^n \rightarrow \{-1,1\}$. We define the noise sensitivity $latex NS(f)$ of a function $latex f$ as $latex NS(f) = P_{x,e}[f(x) \neq f( … Continue reading When did Majority become the stablest?