(Krzysztof Onak continues with Tuesday’s report for Sublinear Algorithms 2011.)

The second part of the day started with a session devoted to the Johnson-Lindenstrauss lemma. Nir Ailon presented different definitions of the problem. In the embedding version, one is given a set of $n$ Euclidean vectors in $\mathbb R^m$ and wants to map them to $\mathbb R^d$, where d is small and the lengths of vectors are preserved up to a factor of $1\pm \epsilon$. It is known that a random projection on $d=O(\epsilon^{-2} \log n)$ dimensions is likely to produce such vectors. The downsides of using a random projection are that both the running time and the required amount of randomness are $\Omega(md)$. Nir has addressed the challenge of reducing these requirements in his papers [Ailon, Chazelle] and [Ailon, Liberty]. His papers employ the Fourier transform and error correcting codes. Nir also discussed a more recently discovered connection between this problem and the restricted isometry property in compressed sensing. This connection resulted in new algorithms for efficiently computing the Johnson-Lindenstrauss transform.

Jelani Nelson presented his recent paper with Daniel Kane. The goal is to give a distribution over sparse matrices that provides the properties required in the Johnson Linderstrauss lemma and can be computed efficiently for sparse vectors. Jelani’s work is a followup to the paper of [Dasgupta, Kumar, Sarlos]. Jelani showed two extremely simple methods for constructing such matrices. In the first, one selects a small number of entries in each column and sets them at random to $-1$ and $1$. In the other one, one partitions the rows into a number of buckets corresponding to the number of desired non-zero entries in each column. Then in each column, one chooses one non-zero entry in each bucket. The main advantage over the approach of Dasgupta et al. is that this way collisions between non-zero entries are avoided. One of the main open questions is to both derandomize the Johnson-Lindenstrauss transform and make it run fast for sparse vectors. Jelani also mentioned a recent follow-up by [Braverman, Ostrovsky, Rabani].

You can spend the following coffee break admiring one of the well preserved frescoes:

Sofya Raskhodnikova talked about the problems of testing and reconstructing Lipschitz functions [Jha, Raskhodnikova 2011]. A function $f:X \to \mathbb R$ is $c$-Lipschitz if for every $x,y \in X$, it holds $|f(x) - f(y)| \le c \cdot |x-y|$. In the testing problem, one wants to verify that a function is approximately Lipschitz (for some fixed $c$). In the reconstruction problem, one wants to design a “local filter” through which the question to a function are asked. If the distance of $f$ to the property of being Lipschitz is $\Delta$, then the filter provides access to a function $f'$ such that $f'$ is Lipschitz, and the distance between $f$ and $f'$ is not much larger than $\Delta$. Sofya mentioned applications of this research to program analysis and data privacy. In her presentation, she focused on the case when the domain $X$ is a hypercube. She gave both positive and negative results, where she mentioned that the latter were greatly simplified by techniques from a recent paper of [Blais, Brody, Matulef].

C. Seshadhri talked about his recent result on submod… Well, Sesh eventually decided to talk about approximating the length of the longest increasing subsequence [Saks, Seshadhri]. Sesh showed that an additive $\delta n$-approximation to the length of the longest increasing subsequence can be computed in $(1/\delta)^{O(1/\delta)} \cdot (\log n)^c$ time, where $n$ is the length of the sequence, $\delta$ is an arbitrary parameter, and $c$ is a constant. Before his work, the best known $\delta$ for which a sublinear algorithm was known was $1/2$. This result also implies a better approximation algorithm for approximating the distance to monotonicity. Sesh showed a simplified version of his algorithm that runs in $(\log n)^{O(1/\delta)}$ time. The algorithm mimics a dynamic program, recursively searches for good splitters, and applies some boosting to obtain a better approximation than $n/2$. Sesh also complained that working on the paper and making everything work was painful. He even explicitely asked: “Was it really worth it?” Sesh, I think it was. This is a really nice result!

At night we experienced earthquakes, with the strongest of magnitude 3.1. It is pretty clear that they were caused by the impression left by today’s talks.

A screenshot from www.emsc-csem.org: