DIMACS is 20

Exactly a week after Friday the 13th was the day of celebration of 20th Anniversary of DIMACS. I was there with my notebook, a journalist for part of the day.

Ron Graham led, talking about embedding graphs into the Hypercube (into {0,1,*}^D space with Hamming like distance). His talk had the rhythm of a Lipton post --- a result, a picture of a researcher, and an anecdote --- and described this discrete math problem from 60's (eg., any graph into embedded into n-1 dimensions) and its modern extensions (eg., strongly connected graphs can be embedded into n^{1+\eps} dimensions).

Peter Winkler went next and spoke about connection between discrete math (DM) and statistical physics (SP). This talk was the clearest I have heard where these connections were made not only in spirit, but via mathematical reductions of problems in SP to DM and vice versa, via examples of SP applicable in DM and vice versa, as well as examples of DM researchers producing nice results in SP and vice versa. Two examples included phase transitions in placing checkers on the board so no two are orthogonally adjacent, and David Reimer's proof of the Van den Berg–Kesten Conjecture.

Eva Tardos spoke about network games. In the general context of studying selfish behavior of agents, Eva explored whether Nash equilibrium is even an interesting goal or product of natural behavior. There is a general, vague agenda out there of the connections between machine learning and game theory, but this talk did a clear exposition, crispy relating Nash equilibrium to no-regret learning outcome (the other way around relates to correlated equilibrium). The final result discussed was by Blum, Even-Dar and Ligett on how routing without regret converges to Nash.

Mike Trick spoke about DIMACS implementation challenges. Lrading with stats and facts, Mike did a great joib of enumerating some of the technical conclusions (tabu search doesn't triumph simulated annealing, practical instances of coloring are easy, random SAT is easy except for phase transition, etc), some of the concrete outcomes (DIMACS data format, library of problem instances, impressive number of citations), and the future possibilities (verify results automatically, web 2.0 methods of blogging and tweeting to connect the community). He quoted John Hooker's work on Heuristics to make the case that a competition is necessarily anti-intellectual and concluded with "We publish losers". I am still struggling with how this challenge from pre-web days (the first version was in 1992 was run through email and ftp) contrasts with the success of NetFlix competition of modern times.

There were two panels. One on education where Henry Pollak made a great point that in education, it is important to look back. The other panel was on DM+TCS in corporate labs, which was predictably depressing, focusing on how to justify DM+TCS research to managers. It clearly emerged that DM+TCS researchers in labs benefitted a lot from the DIMACS community (and vice versa) and DIMACS serves as a neutral ground to bring them together. Marek Rusinkiewicz gave stats and examples. Raj Rajagopalan said DM+TCS researchers in labs served the purpose of Co's being prepared for the future. Michael Pazzani pushed on the theme of patents and it didn't seem like the community either generated significant number of patents or licensed them effectively.

What was the overall impression? I went away feeling DM+TCS researchers needed very little, some travel money, a meeting place, and perhaps some paper and whiteboard. (Mihai Patrascu told me he first wrote with pencil and then overwrote that with pen, so he can reuse paper; therefore, we can half the paper requirement.) They would be happy producing good research. They would not want to be more responsible. :) And the question that lingered in some of the participant's minds: the legacy of early part of DIMACS is impressive, where is it now and where will it be in 10 years.

Rice

X-Mati Rice

Milk

Bala, the raconteur, reminded me how milk is sold and bought in India. The seller brings the cow over, it stands in front of your house, someone checks that the seller's milking jug is empty (eg, has no water), and the seller proceeds to milk the cow into the jug, and pours out the measure for the buyer (the little boy of the house gets the extra foam at the top). The world is finding ways to get back to that. These days, there are fresh milk vending machines which farmers fill directly from their farms and people pour themselves a frothing mug, a la beer. I am told.

NYCE 2009

NY Area CS and Economics (NYCE) II meeting took place on Monday, Nov 6, and was organized by Robert Kleinberg and Eva Tardos.

• Jennifer Rexford led and spoke about interdomain routing in IP networks. She started with a simple model of local rules for path selection that converge to stable paths for routing between IP domains, and later generalized it to picking multiple paths via source dependent path selection. She is an admirably clear speaker on a topic with many details (original RFC here). There were many questions on machine learning (are there algorithms to learn the ``value'' of paths), technology (how to simulate these policies by say MPLS protocols), incentives (domains choosing cheap paths over secure paths, fishing for information via strategic path announcements), and verifiability (can routers send traffic on whatever path they choose despite what they advertise).
• Shahar Dobzinski spoke about truthful polytime approximate mechanisms for multiunit auctions. This was classic AMD material, delivered straight. Questions explored monotonicity (eg quasi-monotonic valuations such as cant use >10k oil barrels) and variance of allocation.
• Michael Kearns showed his theory roots and applied arms. He spoke about matching buy and sell orders, not in light pools where the book shows bid and ask prices, but in the dark pools where only liquidity counts. He proposed an exploration-exploitation approach to buy large orders in dark polls, ultimately deriving RL type algorithms. Questions included role of Crypto protocols (not a good idea to enforce trust, better to remove conflicts in the system design), Strategic orders (to sniff information), and quality of price in light pools (since dark pools set price using light pools but their demand and supply are not reflected in the price at light pools), etc.
  
• Lunch in the financial district is always an exercise in avoiding crowds.
  
• Post lunch, there was a rump session of 5-min talks. Beibei Li spoke about ranking hotels by mining web data. Sharad Goel spoke about pricing ads per impression plus a click cost. Eyal Carmi spoke about quantifying derived effects on an item of a sudden spike in popularity of a related item. Mickey Brautbar spoke about algorithms for finding nodes with high degree (why these are "interesting individuals" is presumably discussed in their ICS paper?). Aaron Jaggard spoke about impossibility results for distributed decisions, from here. Vahab Mirrokni gave a clear talk on quasi-proportional mechanisms and their equilibrium revenue properties. Ruggiero Cavallo spoke about limited amount altruism in auctions. Other talks discussed social network effects to long tail phenomenon.
  
• Larry Blume gave the final talk. He started with several simple examples where we reason about probability, but implicitly with different meanings. He then formally defined different measures of ``probability'' and "expected utilities" including non-additive ones, and worked into applying them to Economic choices agents make. I was overwhelmed by the rich notions of rationality in Economics, and would like to work out some nontrivial examples of applications of these concepts. I liked the narrative in this talk, and Larry is consummate researcher switching between Math and insights, with anecdotes as needed.
  

One of the interesting aspects of NYCE is the audience from business schools to, as it turned out, businesses. The NY Academy of Sciences venue is superb, and the staff run the meeting smoothly.

Goats and Tweets

I watched Men Who Stare at Goats. It is a Catch 22 in 2009 kinda movie, essentially all male, exploring psychics, US Army, goats and LSD. Hilarious and unpredictable. You can't go wrong for acting display putting Kevin Spacey, George Clooney and Jeff Bridges together, goats help.

ps: Twitter turns a movie rater, being a critic however takes more than tweets.

Algorithms and Media

There is a wonderful interview of Michael Rabin about his visit to Google at the university relations page. My favorite part is when he is asked for his advice to students and he says, "algorithms, algorithms, algorithms".

Moti Yung gets cited in Harpers by Barry Eisler.

The phenomenal Ingrid Daubechies is quoted on the game theory behind how to divide a real estate empire threeways: three parties bid, lowest bidder partitions the estate into 3 parts, then a coin flip decides the order among the other two to pick their choice of partition. The goal seems to be to get a envy-free solution.

Need a laugh

A new week will begin soon, we might as well laugh now (SNL Spoof of PBS reviewing a Norwegian Show).