Simons Collaboration on Algorithms and Geometry Monthly Meeting, October 2019

Jarosław Błasiok
An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices

We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that a matrix formed by uniformly subsampling rows of an 𝑁×𝑁 Hadamard matrix contains a 𝐾-sparse vector in the kernel, unless the number of subsampled rows is Ω(𝐾 log 𝐾 log(𝑁/𝐾)) – our lower bound applies whenever min(𝐾,𝑁/𝐾)>log^𝐶𝑁. Containing a sparse vector in the kernel precludes not only the restricted isometry property, but more generally the application of those matrices for uniform sparse recovery.
 

Mikhail Ostrovskii
Geometry of transportation cost (a.k.a. Earth Mover or Wasserstein distance)

We consider (finitely supported) transportation problems on a metric space M. They form a vector space TP(M). The optimal transportation cost for such transportation problems is a norm on this space. This normed space is of interest for the theory of metric embeddings because the space M embeds into it isometrically. I am going to talk about geometry of such normed spaces. The most important questions for this talk are relations of these spaces with L_1 and L_infinity spaces.
 

Fan Wei
Property testing and removal lemma

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to very quickly distinguish between objects that satisfy a certain property from those that are ε-far from satisfying that property. It turns out to be closely related to major developments in combinatorics, number theory, discrete geometry, and theoretical computer science. Some of the most general results in this area give “constant query complexity” algorithms, which means the amount of information it looks at is independent of the input size. These results are proved using regularity lemmas or graph limits. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, of tower-type or worse, as a function of 1/ε, making them impractical. We show by entirely new methods that for permutations, such general results still hold with query complexity only polynomial in 1/ε. We also prove stronger results for graphs through the study of new metrics. These are joint works with Jacob Fox.
 

Jeroen Zuiddam
The asymptotic spectrum of tensors and barriers for fast matrix multiplication

The theory of asymptotic spectra describes asymptotic behavior of basic objects in mathematics like graphs and tensors. Example applications are the matrix multiplication problem, the cap set problem, the sunflower problem, the quantum entanglement problem, and the problem of efficient communication over a noisy channel.

In this talk we will focus on one application: the matrix multiplication problem. We will use the asymptotic spectrum of tensors to prove that a very general method, which includes the methods used to obtain the currently best algorithms, cannot give faster matrix multiplication algorithms.