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.

First, let me say that I didn’t attend, but from reading others’ blogs, I gathered these must-reads:

• Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes, Ailon, Liberty, SODA’08: I started reading this. It’s really nice. It improves Chazelle & Ailon’s FJLT by noticing that the worst-case is unlikely. Then it proceeds to use elegant techniques from Banach theory and coding
• Clustering for Metric and Non-Metric distance measures, Ackermann, Blomer, Sohler, SODA’08: This was recommended by The Geomblog
• Declaring Independence via Sketching of Sketches, Indyk, McGregor, SODA’08: This one I’ve actually read. This paper scratches the surface of a new subject of sensing statistics of matrix-like objects. The main open question (rephrased) of this paper is this:
  

  If a matrix is streamed (as element-wise updates), can you approximate , where ?

  On a related note, I will mention another open question (pertaining to streaming algorithms on matrices) without motivating it much (feel free to ask me for details): Can one “take the square root of a desired unimodal origin-symmetric distribution W”. I.e. is there some magical distribution Q, so that if X~Q and Y~Q then X*Y~W? E.g. when W is taken to be some p-stable distribution, one can use its (convolutional) square root Q to approximate -norms of the singular values vector of a streaming matrix in the rotated space. I am mentioning this question because no one seems to know the answer or have any intuition about it. Yet the question is natural and of a classical type (in Harmonic Analysis)

• Finally, Mitzenmacher’s blog reports that Diaconis’ talk on the relationship between carry, shuffling and Young tableux is quite fascinating

At this point I open the stage for you guys to tell me about other great picks.