Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms

Edited by Claire Mathieu

Preface and Acknowledgements

We were very pleased to choose papers for presentation at the ACM-SIAM Symposium on Discrete Algorithms (SODA), which will take place in Manhattan in January 2009. A total of 550 short abstracts were submitted, later materializing into 458 submissions, of which 135 were selected. The program committee meeting was entirely electronic and the selection process took place in July and August 2008. The Best Student Paper award was given to the paper "Improved Bounds and New Techniques for Davenport–Schinzel Sequences and Their  Generalizations" by Gabriel Nivasch, and the Best Paper award was given to the paper  "Natural Algorithms" by Bernard Chazelle. There will be three invited presentations: one by Volker Strassen, as the recipient of the ACM-SIGACT 2008 Knuth prize; one by Michael Jordan; and one by Yuval Peres.

I would like to thank the program committee for their hard work:

We tried to exercise our best judgment in choosing the submissions that seemed most interesting for the SODA audience. In that work, we were helped by the hundreds of dedicated subreviewers who freely gave their time and effort to help our evaluation. I was impressed by their rapid response to queries and the depth of their reading, and am grateful for their contribution. Most people accepted requests for reviews without hesitation, and their opinions provided crucial input for our decisions. This is what makes SODA a great conference!

Thanks are also due to Microsoft Research, for its sponsorship; to Easychair, for managing the program committee meeting Web site; to Shay Mozes, for helping with Web features; and to Kirsten Wilden and other members of the SIAM staff for their help.

Most of all, I wish to thank the authors of submissions, both accepted and rejected. Errare humanum est. I am sure that we made some imperfect choices, as inevitably happens with every committee, and offer my apologies to those whose work may have been slighted. 

This year there was a new feature that particularly pleased me: the requirement that authors submit results with full proofs, using an appendix if necessary. This enabled us to find several flaws in the proofs, sometimes minor, sometimes critical. Several submissions probably never materialized because the authors, during the process of spelling out their proofs in detail, came upon unexpected difficulties that would otherwise have been overlooked.  I believe that the final papers are much stronger as a result of this requirement.

Here are the accepted papers that have all-student authors: "Robust PCA and Clustering in Noisy Mixtures" (by S. Charles Brubaker), "Improved Bounds and New Techniques for Davenport–Schinzel Sequences and Their Generalizations" (by Gabriel Nivasch), "Towards Computing the Grothendieck Constant"  (by Prasad  Raghavendra and David Steurer), "On the Complexity of Nash Equilibria of Action-Graph Games" (by Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant), and "Loopless Generation of Multiset Permutations Using a Constant Number of Variables by Prefix Shifts" (by Aaron Williams). La valeur n'attend pas le nombre des années! I see that as a witness both to the energy and enthusiasm of the student authors, and to the lively atmosphere of their departments. I wish I had done the same when I was a student.

How can advisors encourage such work? I asked the authors of student-only papers for their opinions, and here is their diverse feedback: The key is "camaraderie: having friends with whom discussions of one's ideas and work happen naturally." For example, student-only seminars provide a casual environment where collaborations may spawn.  Students may hesitate to work independently when their financial support comes from a faculty's individual grant: A proactive attitude on the advisor's part is needed to overcome psychological barriers.  "A certain amount of luck is always involved, but it greatly helps if the advisor gives continuous support and encouragement in facing topics that look intimidating at first."  Or sometimes, the work simply "grows out of a well-designed class project" (a great satisfaction for the instructor). Finally, location matters: If the conference happens at a place to which students want to travel, it gives them additional motivation. In any case, I extend my congratulations to this particular crop of authors. 

Finally, I hope that our research community will enjoy listening to the talks at the conference, discussing the results and techniques with the authors, reading the papers, and advancing the research in our fields. Have fun!

Claire Mathieu
Program committee chair

Acknowledgments

The SODA 2009 Program Committee thanks the following colleagues, who willingly gave their help and time to read and review SODA 2009 submissions.

Scott Aaronson
Mohammad Abam
James Abello
Ittai Abraham
Dimitris Achlioptas
Louigi Addario-Berry
Isolde Adler
Pankaj Agarwal
Gagan Aggarwal
Nir Ailon
Adi Akavia
Susanne Albers
David Aldous
Luca Castelli Aleardi
Lyudmil Aleksandrov
Noga Alon
Helmut Alt
Christoph Ambuhl
Omid Amini
Aris Anagnostopolous
Kent Andersen
Reid Andersen
Alexandr Andoni
Matthew Andrews
Miguel Anjos
Barbara Anthony
Aaron Archer
Boris Aronov
Diego Arroyuelo
Abdullah Arslan
David Arthur
Arash Asadpour
Alper Atamturk
Dominique Attali
Peter Auer
Salman Avestimehr
Chen Avin
David Avis
Yossi Azar
Moshe Babaioff
Brian Babcock
Bahman Bahmani
Maria-Florina Balcan
Nikhil Bansal
Gill Barequet
Surender Baswana
Mohammad Hossein Bateni
Tukan Batu
Mohsen Bayati
Paul Beame
Amos Beimel
Eli Ben-Sasson
Michael Bender
Jur van den Berg
Mark de Berg
Eli Berger
Piotr Berman
Marshall Bern
Alina Beygelzimer
Shankar Bhamidi
Nayantara Bhatnagar
Dan Bienstock
Benjamin Birnbaum
Avrim Blum
Manuel Bodirsky
Hans L. Bodlaender
Jean-Daniel Boissonnat
Flavia Bonomo
Paul Bonsma
Jit Bose
Andreas Brandstaedt
Peter Brass
Mark Braverman
Anat Bremler-Barr
Patrick Briest
Gerth Brodal
Nicolas Broutin
Daniel Brown
Niv Buchbinder
Kevin Buchin
Luciana Buriol
Sergiy Butenko
Lilian Buzer
Sergio Cabello
Alberto Caprara
Marcelo Henriques Carvalho
Amit Chakrabarti
Erin W. Chambers
Timothy Chan
Pierre Charbit
Kamalika Chaudhuri
Swarat Chaudhuri
Shuchi Chawla
Frédéric Chazal
Bernard Chazelle
Chandra Chekuri
Jianer Chen
Ke Chen
Ning Chen
Ting Chen
Xi Chen
Ho Lun Cheng
Victor Chepoi
Andrew Childs
Gregory Chockler
Demetres Christofides
Marek Chrobak
Edith Cohen
David Cohen-Steiner
Amin Coja-Oghlan
Richard Cole
Vincent Conitzer
Colin Cooper
Martin Cooper
Robert Cori
Graham Cormode
Jose Correa
Russ Cox
Maxime Crochemore
Artur Czumaj
Sanjoy Dasgupta
Constantinos Daskalakis
Brian Dean
Daniel Delling
Jesus De Loera
Xiaotie Deng
Nikhil Devanur
Olivier Devillers
Matt DeVos
Tamal K. Dey
Walter Didimo
Martin Dietzfelbinger
Bistra Dilkina
Ned Dimitrov
Guoli Ding
Shahar Dobzinski
Benjamin Doerr
Shaddin Doghmi
Frederic Dorn
Laurent Doyen
Petros Drineas
Michael Drmota
Donglei Du
Vida Dujmović
Adrian Dumitrescu
Dominik Dumrauf
Bruno Durand
Christoph Durr
Martin Dyer
Wayne Eberly
Herbert Edelsbrunner
Khaled Elbassioni
Faith Ellen
Robert Elsaesser
Yuval Emek
Alexander Engau
Matthias Englert
David Eppstein
Leah Epstein
Funda Ergun
Jeff Erickson
Thomas Erlebach
Daniel Espinoza
Kousha Etessami
Eyal Even-Dar
Hazel Everett
Marcia Fampa
Martin Farach-Colton
Mohammad Farshi
Babak Farzad
Uriel Feige
Sandor Fekete
Dan Feldman
Stefan Felsner
Cristina Fernandes
Antonio Fernandez
Jiri Fiala
Amos Fiat
Irene Finocchi
Eldar Fischer
Abraham Flaxman
Lisa Fleischer
Fedor Fomin
Jan Foniok
Bernard Fortz
Jacob Fox
Alexandra Fradkin
Pierre Fraigniaud
Tom Friedetzky
Alan Frieze
Stefan Funke
Eric Fusy
Bernd Gaertner
Jie Gao
Leszek Gąsieniec
Cyril Gavoille
Loukas Georgiadis
Robert Ghrist
Joachim Giesen
Aris Gionis
Frederic Giroire
Marc Glisse
Xavier Goaoc
Brighten Godfrey
Ashish Goel
Sharad Goel
Leslie Ann Goldberg
Sharon Goldberg
Daniel Gonçalves
Laureano González-Vega
Michael Goodrich
Lee-Ad Gottlieb
Navin Goyal
Fabrizio Grandoni
Timothy Griffin
Martin Grohe
Bertrand Guenin
Sudipto Guha
Jiong Guo 
Anupam Gupta
Venkatesan Guruswami
Vladimir Gurvich
Gregory Gutin
Bernd Gärtner
Michel Habib
MohammadTaghi Hajiaghayi 
Iman Hajirasouliha
Magnus Halldorsson
Nir Halman
Michael Halperin
Sariel Har-Peled
Boulos Harb
Jason Hartline
David Hartvigsen
Nick Harvey
Joel Hass
Refael Hassin
Herman Haverkort
Monika Henzinger
Dan Hirschberg
Petr Hlineny
John Hobby
Martin Hoefer
Thomas Holenstein
Andreas Holmsen
Nick Hopper
Samuel Hornus
Heikki Hyyrö
John Iacono
Nicole Immorlica
Piotr Indyk
Tigran Ishkanov
Satoru Iwata
Mark Iwen
Riko Jacob
Ali Jadbabaie
T.S. Jayram
Iwan Jensen
Albert Xin Jiang
Ramesh Johari
David Johnson
Hossein Jowhari
Sham Kakade
Adam Kalai
Satyen Kale
Erez Kantor
Ming-Yang Kao
Haim Kaplan
Adriana Karagiozova
Anna Karlin
Howard Karloff
Shiva Kasiviswanathan
Tali Kaufman
Michael Kaufmann
Henry Kautz
Ken-ichi Kawarabayashi
Michael Kearns
Peter Keevash
Hans Kellerer
David Kempe
Walter Kern
Alex Kesselman
Sanjeev Khanna
Subhash Khot
Samir Khuller
Yongdae Kim
Guy Kindler
Tamas Kiraly
Stefan Kirchner
David Kirkpatrick
Adam Kirsch
Martin Klazar
Rolf Klein
Philip Klein
Jon Kleinberg
Christian Knauer
Thorsten Koch
Patrice Koehl
Alexandra Kolla
Jochen Konemann
Aleksandra Korolova
Guy Kortsarz
Christoph Koutschan
Daniel Kral
Jan Kratochvil
Dieter Kratsch
Robert Krauthgamer
Bhaskar Krishnamachari
Michael Krivelevich
Nico Kruithof
John Krumm
Gregory Kucherov
Alexander Kulikov
Brian Kulis
Amit Kumar
Ravi Kumar
Sebastien Lahaie
Tak-Wah Lam
Fumei Lam
Nicholas Lambert
Gad Landau
Michael Langberg
Stefan Langerman
Lap Chi Lau
Monique Laurent
Ron Lavi
Sylvain Lazard
Francis Lazarus
Stefano Leonardi
Asaf Levin
Meital Levy
Moshe Lewenstein
Fei Li
André Lieutier
Nati Linial
Marina Lipshteyn
Sylvain Lombardy
Zvi Lotker
Vadim Lozin
Eyal Lubetzky
George Lueker
Nelson Maculan
Mohammad Mahdian
Yury Makarychev
Kostya Makarychev
Elitza Maneva
David F Manlove
Yishay Mansour
Russell Martin
Conrado Martinez
Daniel Marx
Monaldo Mastrolilli
Jiří Matoušek
Arie Matsliah
Tom McCormick
Colin McDiarmid
Andrew McGregor
M. Douglas McIlroy
Brendan McKay
Frank McSherry
Nicole Megow
Henk Meijer
Manor Mendel
Julian Mestre
Daniele Micciancio
Milena Mihail
Peter Bro Miltersen
Vahab Mirrokni
Joe Mitchell
Flavio Miyazawa
Bojan Mohar
Michael Molloy
Andrea Montanari
Ravi Montenegro
Pat Morin
Dmitriy Morozov
Walter Morris
Elchanan Mossel
David Mount
Bernard Mourrain
Ahuva Mu'alem
Abubakr Muhammad
Elena Mumford
Kamesh Munagala
Ian Munro
Masakazu Muramatsu
S. Muthu Muthukrishnan
Petra Mutzel
Shubha Nabar
Asaf Nachmias
Uri Nadav
Kiyohito Nagano
Seffi Naor
Gonzalo Navarro
Jelani Nelson
Ilan Newman
Rolf Niedermeier
Taishin Nishida
Kobbi Nissim
Gabriel Nivasch
Sergey Norin
Zeev Nutov
Martin Nöllenburg
Ryan O'Donnell
Joseph O'Rourke
Yoshio Okamoto
Krzysztof Onak
Deryk Osthus
Rafail Ostrovsky
Steve Oudot
Sang-l Oum
Rasmus Pagh
Martin Pal
Ondrej Pangrac
Alois Panholzer
Rina Panigrahy
Gyula Pap
Kenny Paterson
Mihai Patrascu
Anindya Patthak
Chris Peikert
Javier Pena
David Pennock
Seth Pettie
Florian Pfender
Jeff Phillips
Vincent Pilaud
Ross Pinsky
Leonidas Pitsoulis
Greg Plaxton
Oleg Prokopyev
Fabio Protti
Srinivas R.
Yuri Rabinovich
Luis Rademacher
Jaikumar Radhakrishnan
Tomasz Radzik
Harald Raecke
Prasad Raghavendra
Daniel Raible
Vijay Ramachandran
Dana Randall
Anup Rao
Sofya Raskhodnikova
Dieter Rautenbach
Dan Reeves
Joachim Reichel
John Reif
Mauricio Resende
Heiko Roeglin
Günter Rote
Tim Roughgarden
Natan Rubin
Atri Rudra
Matthias Ruhl
Ignaz Rutter
Kunihiko Sadakane
Bardia Sadri
Amit Sahai
Cenk Sahinalp
Mike Saks
Mohammad Salavatipour
Robert Samal
Peter Sanders
Piotr Sankowski
Tamas Sarlos
Thomas Sauerwald
Francesco Scarcello
Nicolas Schabanel
Mathias Schacht
Christian Scheideler
Grant Schoenebeck
Warren Schudy
Leonard Schulman
Andreas S. Schulz
Oded Schwartz
Pascal Schweitzer
Bob Sedgewick
Raimund Seidel
Taral Seierstad
Meinolf Sellmann
Charles Semple
Rocco Servedio
Jay Sethuraman
Devavrat Shah
Andrew Shallue
Asaf Shapira
Aneesh Sharma
Yogeshwer Sharma
Bruce Shepherd
Hanif Sherali
Akiyoshi Shioura
Amnon Ta Shma
Vitaly Shmatikov
Adi Shraibman
Anastasios Sidiropoulos
Alistair Sinclair
Rashi Sinha
Rene Sitters
Alexander Skopalik
Martin Skutella
Alex Slivkins
Allan Sly
Shakhar Smorodinsky
Jack Snoeyink
Christian Sohler
Eric Sopena
Gregory Sorkin
Alexander Souza
Cid de Souza
Aravind Srinivasan
Nikhil Srivastava
Nisheeth Srivastava
Angelika Steger
Clifford Stein
Paul Stockmeyer
Miloš Stojaković
Martin Strauss
Torsten Suel
Jian Sun
Mukund Sundararajan
Ola Svensson
Zoya Svitkina
Chaitanya Swamy
Stefan Szeider
W. Szpankowski
Tami Tamir
Anusch Taraz
Robert Tarjan
Tamir Tassa
Monique Teillaud
Kavitha Telikepalli
Jan Arne Telle
Evimaria Terzi
Prasad Tetali
Dimitrios Thilikos
Shripad Thite
Michael Todd
Andrew Tomkins
Eric Torng
Csaba Tóth
Géza Tóth
Avraham Trakhtman
Luca Trevisan
Nicolas Trotignon
Paul Tseng
Takashi Tsuchiya
Eduardo Uchoa
Chris Umans
Jan Vahrenhold
Vincent Vajnovszki
Mario Valencia-Pabon
Marc van Kreveld
Kasturi Varadarajan
Vinodchandran Variyam
Sergei Vassilvitskii
Yann Vaxès
Erik Vee
Santosh Vempala
Suresh Venkat
Suresh Venkatasubramanian
Elad Verbin
Adrian Vetta
Stéphane Vialette
Antoine Vigneron
Eric Vigoda
Danny Vilenchik
Emanuele Viola
Berthold Voecking
Jan Vondrak
Sergei Vorobyov
Grant Wang
Ian Wanless
Shmuel Weinberger
Rephael Wenger
Carola Wenk
Renato Werneck
Tom Wexler
Udi Wider
Gordon Wilfong
Ryan Williams
Peter Winkler
Alexander Wolff
Paul Wollan
Nicola Wolpert
David Wood
David Woodruff
Camille Wormser
David Xiao
Qiqi Yan
Qiushi Yang
Yinyu Ye
Sergey Yekhanin
Anders Yeo
Neal Young
Raphael Yuster
Mariette Yvinec
Giacomo Zambelli
Riccardo Zecchina
Mariano Zelke
Luis Zuluaga
Uri Zwick
Yori Zwols

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account