The MMDS Workshop

I was at the workshop on Algorithms for Modern Massive Data Sets (MMDS), organized by Petros Drineas and Michael Mahoney with Gene Golub and Lek-Heng Kim, June 21--24, at Stanford U. (yeah, yeah, good weather, resort-like campus, students wearing rich clothes). The workshop was highly oversubscribed and somewhat dense with talks. Still, it is among one of the best workshops I have attended, with a terrific collection of speakers and lot of good talks on math---numerical analysis, linear algebra, algorithms---and applications.

- Diane Leary gave an overview of matrix decomposition methods, much appreciated! She also used the word "downdate" (as opposed to the positive "update"), therefore giving me the license to late use "postcursor" in my talk. She pointed out a mathematician with the carplate "Prof. SVD".
- Michael Mahoney described interesting way to apply row and column sampling methods for low rank approximation to a variety of problems from genetics, medical imaging and recommendation systems. Cool!
- Prabhakar Raghavan gave his talk from STOC. He did a very good job of not just representing Yahoo! but rather, presenting large areas for research in the domain of internet search, services and software. First, he spoke about Flickr and posed label inference problems on graphs. Second, he spoke about auctions for keyword searches on the internet. He mainly described the properties of Yahoo! and Google auctions, with bulk of the technical results from the paper Internet Advertising and Generalized Second Price Auction by Edelman, Ostrovsky and Schwarz. He mentioned that Google auctions were locally envy-free, but did not go further to describe other properties such as bidder-optimal (ie, total paid by advertisers is minimum among such equilibria). He mentioned interesting problem of determining the granularity of the market to bid. Third, he described Yahoo Answers, and spoke about a speculative p2p version of it from his paper on Query incentive networks with Kleinberg. There are a lot of interesting theoretical open problems here, and a lot of interesting mechanism design questions in general in the area. Organizationally, companies have traditionally had three different groups: research, development and marketing. Some of the companies are succeeding in merging research and development, not just in name. Prabhakar pointed out that in the future all the groups may have to be integrated since pricing/economics and marketing are inherently part of research and development of systems and services.
- There was a session of topology and learning. I finally understood a little about persistent homology that Edelsbrunner and others have worked on, and the excitement around it in the applied math community. A speaker in this session said, "So you go ahead and build the simplicial complex because it is a common thing to do." Smale said, "I have trouble telling the left from the right, or > from <."
- I spoke about algorithmic theory of sparse approximation problems with vectors and in particular, discussed Compressed Sensing problems. Since my talk was mainly on vectors and the audience was primed for matrices and tensors, they had to adjust to the notation. I was happy to hear from several applied mathematicians that they were surprised that even in the simplest vector context, some of the very basic problems were open from the point of view of algorithms and complexity. I was trying to communicate just that with for example, the nonuniform sparse approx problems.

Alas, I could not go to a lot of other talks. I had to work too. :) The organizers have set up a nice site with slides of the talks. I wish the organizers would write a report on this meeting for wide circulation, because it succeeded so well in bringing the applied math communities together. Finally, it was great to see so many students at this meeting! Bravo.