Alex Samorodnitsky talked about LP bounds for coding at MIT. A few small things I wanted to jot down follow. Delsarte was the first one to attempt an LP-type bound for coding. It sounded that his work would be interesting to read as establishing the actual bound went through some algebra and some geometry. In 1989 Kalai-Linial publish a Fourier-based approach to the analysis of Delsarte’s LP. Alex suggested that this may be the first time Fourier is used in Computer Science. The LP bound, which is essentially a packing bound for the Hamming cube, has counterparts in Mathematics regarding packings in metric spaces. Alex’s latest paper (S’08) has references to all these, but it is not available yet. So a related link is a previous paper of his and Navon’s.

A note to myself: MIT’s undergraduate class on PDEs uses these two books:

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

The crazy title up there means “recovering a 3D model of a molecule, using multiple 2D images/projections”. This was a talk at MIT by Yoel Shkolnisky. The talk was really neat, but the bottom line is this. From a CS point of view he was solving the following question. We have n points that (we know) come from some finite metric. We are given the pairwise distances (+ noise) between points that are within each other’s vicinity (in that metric). The goal is to reconstruct the metric. I’ve phrased this problem a little more generally then the form in which it is addressed in Yoel’s work.

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.

MIT has a lunch for students and professors in the Theory of Computation group, where one can eat pizza and here other people’s casual open problems. Sometimes really cute problems and/or discussions fall out. Today (non-exhaustive):

• 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?

Spectral Graph theory has various methods of bounding the Laplacian eigenvalues of a graph G (say by embedding another graph H into G and computing the congestion). Usually we look at the ordered eigenvalues , and usually we simplify things a little by assuming a bounded-degree graph, which gives us for free, where is the maximum vertex degree. So really, it is mostly just interesting to bound from below. When this is done, it is very often used as (when bounding energy of electrical flows in G) or as (when bounding mixing times of random walks on G).

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.

I believe one day I will look back and wonder, what have I had for breakfast all those years. What are my ingredients, so to speak. Here’s what I had today then:

• Naked “Orange Mango Motion” juice — all natural and it has 100% of something
• Fage greek yoghurt — the best yoghurt on the market. Keep in mind that I am Bulgarian. We have the best yoghurt bacteria in the world. So if I tell you that Fage is awesome-est, then it is
• Flaxseed Oil — this, my friends, is the secret ingredient which when mixed with the yoghurt (above) turns you into a gladiator
• A plain croissant — often all that one needs for a successful day, croissant and coffee and off you go

And, if you are questioning what is so fascinating about my breakfast: I prepended some yoga before it, which essentially doubles the pleasure of anything that comes afterwards — breakfast and work alike!