• Partial differential equations, Strauss
• Partial differential equations, Fritz John

The key idea in his work is to learn a basis that is good for images. Such basis will have to give up the universality property, but this is OK. Learning such a basis is done by taking a big collection of images and trying to find a basis where all images have sparse representations that are not too far (in L2 sense) from the original images. It turns out that a relatively simple iterative algorithm, involving linear regression at each step, does the job just fine. The results are stunning! Images come out with practically perfect quality. 

According to Sapiro, his papers are not theoretical-theoretical, in the sense that there are no proofs of “rigid” statements as one typically wants in the theory community. The usefulness of the algorithms is exhibited by look-and-feel. As one might imagine, these techniques have various applications beyond just sensing and compressing. One can do (what Sapiro calls) inpainting. This is when you are given an image missing a large fraction of its pixels or an image with a low signal-to-noise ration. If you like to “fill-in” the missing (or noisy) pixels, all you need to do is find the sparse representation of the given image that is closest in norm to the noisy original. Once again, results are stunning visually.

Lastly, this technique theme can be used for classification of the sort where you say “this image depicts cows rather than cars”. The trick here is that one learns a basis for cars and for cows such that the car basis is additionally optimized to perform intentionally bad on cows and vice-versa. The learning of such bases is a slightly more complicated version (there is an added condition) of the basic learning algorithm mentioned earlier.

Discrete unit-circle cover in the plane

A problem instance is given by a set of points in the plane and a set of unit discs. The goal is to find the smallest subset of the discs that covers all points. This problem is NP-complete (surprisingly). The open question is: Can you -approximate the optimum (for any )?

Bicriteria unit-circle cover in the plane

My recollection on this one may be slightly off. It’s the same problem as above, but you are shooting for a bicriteria algorithm where you are allowed to expand the given discs by a small , so the bicriteria is in . The question here may have been, what is the smallest disc expansion for which you can get a bicriteria solution equal to the optimum (without disc expansion).

Paul Valiant’s Canonical Tester is a one-stop-shop solution for testing any symmetric property of a distribution. If the Canonical Tester can’t do it, neither can you. The additional upshot is that the Canonical Tester is quite simple an algorithm, so proving lower bounds (impossibility results) usually takes short 5-line arguments explaining why the Canonical Tester can’t do it.

Testing asymmetric properties is now the next interesting question. Interesting it is indeed because most practical questions actually tend to involve asymmetric properties. A modified example of Paul’s talk goes like this. Imagine Amazon makes a change on their website, and they like to know whether more books compared to electronics were sold after the change. This is an asymmetric test.

• Stateless Distributed Gradient Descent for Positive Linear Programs, Awerbuch, Khandekar, STOC’08
• Stateless Near Optimal Flow Control with Poly-logarithmic Convergence, Awerbuch, Khandekar, LATIN’08

The cool thing is that Yoel et al. solve this problem using a very natural appeal to graph Laplacians. This is found in a technical report on his page. Amit Singer (a collaborator) additionally has a paper on using these techniques to recover the global metric of sensor networks, based on local distance information. This is found in the form of a paper on Amit’s webpage.

There might be an opportunity for a new paper lurking in there. In particular, it is interesting to ask under what noise conditions (and noise can be correlated in real-world examples) is the recovery good. Having heard the talk, I believe that the answer to this question will also depend on the type of metric being recovered, i.e. it may depend on its doubling dimension e.g.

Oh, I should also mention that Yoel seems to have some cool papers involving the discrete Radon transform. This is probably a good place to read about it, while avoiding the continuous lingo.

• Alexandr Andoni asked — Consider the following Shifted Hamming (SH) distance on bit strings. The distance between two strings is defined as the Hamming distance after shifting (really rotating) one of the strings by an arbitrary amount (which produces the smallest Hamming distance). The questions are. Can we embed the SH metric into the Hamming metric with low distortion? If I am not mistaken, Alex knows a lower bound on the distortion of O(log n) using a Fourier argument. And, can we embed SH into (the squared Euclidean norm)? I believe no lower bound is known here and O(1) may be possible.
• Ron Rivest is working on an intentionally very simple election auditing system, which hinges on a pseudorandom function that can be computed on a handheld calculator in a few strokes. The detailed description of the procedure is on his website (I couldn’t find, but it is there!). Ron asked if there are any obvious attacks/problems with his design. His question brought up a somewhat simpler question that seems very curios to me: Pick a random integer between 1 and 1000, take its square root, and consider the first bit of its fractional part. How far is the distribution of that bit from uniform?

We are interested in a new type of Laplacian bounds. It turns out that L1 bounds of the sort relate directly to how good electrical flow is when used for oblivious routing on G. Note that it is required here that since is the kernel of the Laplacian of any connected graph. This sort of bound is atypical in two ways. First, it is an L1 bound, and second, it is a lower-bound.

It is trivial to see that where is the Laplacian of the n-clique. What we are after is proving that

where H is an expander and and .

This statement holds true in experiments with random bounded-degree expanders, and in particular it has natural interpretations in terms of electrical flow (which I am going to omit here). One can even give a pseudo-proof of this fact by simply observing that .

I am curious if someone has come across similar types of inequalities and/or has an interesting proof idea.

Note that the above conjecture was recently proven and its proof will soon appear in a publication. I will post a link to it here when this happens. At this stage will be happy to hear of applications of this (now) theorem if you come across any.

It’s only appropriate to mention that our own Donald Knuth has made one of the most significant impacts on modern-day (industrial) typesetting. His work is detailed in his books, however one can get the gist of it in his lecture notes Mathematical Typography (dedicated to George Polya). This article describes two revolutionary ideas. One is the idea that text layout can be cast as a dynamic program. This is taught in many algorithms classes and as simple as it may be, it completely overwrites what was done for hundreds of years beforehand. The second, is the idea of meta font design where a font is specified by a bare-bone description of the letters’ structure and the rest (the style and look) is described using 60-something mathematical parameters (i.e. numbers).

A few fonts of my choice:

• Helvetica by Max Miedinger. No comment necessary
• FF Meta by Erik Spiekermann
• ITC Officina by Erik Spiekermann
• Escrow by Cyrus Highsmith, commissioned and used by the Wall Street Journal
• Moderno FB by David Berlow. This font has the same roots as the all known Computer Modern used in the TeX system
• FF Meta Serif by Kris Sowersby