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.
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.
Labels: aggregator
posted by metoo at 3:12 AM
0 Comments:
Post a Comment
<< Home