
Preface and Acknowledgments
The papers in this volume were presented at the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, held January 23–25, 2011 in San Francisco, California. The Symposium was jointly sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory) and by the SIAM Activity Group on Discrete Mathematics.
The program committee accepted 136 submissions of the 452 that were submitted. There were 526 short abstracts submitted at the early registration deadline, resulting in 459 full papers, 7 of which were withdrawn early in the review process. Two pairs of accepted submissions were merged and two more subsequently withdrawn, resulting in 132 presentations at the conference and 133 publications. Papers were chosen based on originality, technical contribution, and relevance. The committee was helped immensely in this process by input from nearly 600 external reviewers. We are very grateful to them for their invaluable help.
The submissions were not formally refereed, although a sincere attempt was made to verify the main claims and to provide detailed feedback to authors. It is expected that most of the accepted papers will appear subsequently (possibly in more complete form) in scientific journals.
The program committee awarded the Best Paper award to:
An Almost Optimal Unrestricted Fast Johnson–Lindenstrauss Transform, Nir Ailon and Edo Liberty.
The Best Student Paper award was given jointly to two papers:
Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components, Jakub Łącki, and An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter, Shay Solomon.
In addition, we invited three speakers to present plenary talks at the conference: Timothy Chan, William Freeman, and Bruce Reed.
The program committee thanks all the authors for supporting the conference with their submissions.
We thank David Johnson and Prasad Tetali for their guidance throughout the process. We are grateful to Randy Carpenter and Peter Wan for their help setting up the HotCRP software and hosting the conference server at Georgia Tech. Kirsten Wilden of SIAM was particularly helpful at keeping the whole process running smoothly, and we are grateful to her, Jennifer Fasy, Gina Rinelli, and other members of the SIAM staff for their support.
Finally, I would like to personally thank the program committee for their enormous effort, their expertise, and their dedication to maintaining the excellence of this conference.
Dana Randall
SODA 2011 Program Committee Chair
The SODA 2011 Program Committee
Glencora Borradaile,
Oregon State University, USA |
Shuchi Chawla,
University of Wisconsin, Madison, USA |
Edith Cohen,
AT&T Labs-Research, USA |
Artur Czumaj,
University of Warwick, United Kingdom |
David Eppstein,
University of California, Irvine, USA |
Vitaly Feldman,
IBM Almaden, USA |
Anna Gilbert,
University of Michigan, USA |
Mordecai Golin,
Hong Kong University of Science and Technology, Hong Kong |
Navin Goyal,
Microsoft Research, India |
Catherine Greenhill,
University of New South Wales, Australia |
Sudipto Guha,
University of Pennsylvania, USA |
Anupam Gupta,
Carnegie Mellon University, USA |
Sean Hallgren,
Pennsylvania State University, USA |
Piotr Indyk,
Massachusetts Institute of Technology, USA |
Satoru Iwata,
Kyoto University, Japan |
Kamal Jain,
Microsoft Research, Redmond, USA |
Satyen Kale,
Yahoo Research, USA |
David Karger,
Massachusetts Institute of Technology, USA |
Jonathan Katz,
University of Maryland, USA |
Ken-ichi Kawarabayashi,
National Institute of Informatics, Japan |
David Kempe,
University of Southern California, USA |
Valerie King,
University of Victoria, Canada |
Michael Molloy,
University of Toronto, Canada |
Seffi Naor,
Technion, Israel |
Mihai Patrascu,
AT&T Labs-Research, USA |
Harald Räcke,
University of Warwick, United Kingdom |
Prasad Raghavendra,
Microsoft Research, New England, USA |
Dana Randall (chair),
Georgia Institute of Technology, USA |
David Shmoys,
Cornell University, USA |
Ileana Streinu,
Smith College, USA |
Acknowledgments
The program committee thanks the following colleagues who generously
gave their help and time to read the review SODA 2011 submissions.
Scott Aaronson
Ittai Abraham
Dimitris Achlioptas
Anna Adamaszek
Michal Adamaszek
Peyman Afshani
Shipra Agrawal
Kook Jin Ahn
Nir Ailon
Susanne Albers
Peter Allen
Noga Alon
Andris Ambainis
Nina Amenta
Alexandr Andoni
Elliot Anshelevich
Aaron Archer
Takao Asano
Mike Atkinson
Per Austrin
Pranjal Awasthi
Yossi Azar
David Bacon
Christel Baier
Doru-Cristian Balcan
Maria Florina Balcan
Nikhil Bansal
Imré Barany
Magali Bardet
Siddharth Barman
Alexander Barvinok
Surender Baswana
Tugkan Batu
Mohsen Bayati
Wolfgang Bein
Shai Ben-David
Petra Berenbrink
Tanya Berger-Wolf
Daniel Bernstein
Umang Bhaskar
Nayantara Bhatnagar
Arnab Bhattacharya
Sayan Bhattacharya
Peter Biro
Troels Bjerre Sørensen
Markus Blaeser
Guy Blelloch
Andrej Bogdanov
Jean-Daniel Boissonnat
Beate Bollig
Mireille Bousquet-Melou
Patrick Briest
Yuriy Brun
Niv Buchbinder
Jaroslaw Byrka
Sergio Cabello
Leizhen Cai
Gruia Calinescu
Alberto Caprara
Keren Censor-Hillel
Tanmoy Chakraborty
Ho-Leung Chan
Timothy Chan
Moses Charikar
Krishnendu Chatterjee
Frederic Chazal
Chandra Chekuri
Ho-Lin Chen
Ning Chen
Po-An Chen
Xi Chen
Yijia Chen
Nathan Chenette
Qi Cheng
Siu-Wing Cheng
Yun Kuen Cheung
Andrew Childs
Eden Chlamtac
Rezaul Alam Chowdhury
Demetres Chrisofides
Giorgos Christodoulou
Marek Chrobak
Maria Chudnovsky
Julia Chuzhoy
Kenneth Clarkson
Raphael Clifford
Elad Cohen
Reuven Cohen
Henry Cohn
Amin Coja-Oghlan
Richard Cole
Éric Colin de Verdière
David Conlon
Graham Cormode
Nicolas Courtois
Andrzej Czygrinow
Anirban Dasgupta
Constantinos Daskalakis
Lior Davidovitch
Brian Dean
Erik Demaine
Amit Deshpande
Vin de Silva
Nikhil Devanur
Luc Devroye
Ronald de Wolf
Ilias Diakonikolas
Josep Diaz
Martin Dietzfelbinger
Alex Dimakis
Jian Ding
Michael Dinitz
Irit Dinur
Shahar Dobzinski
Yevgeniy Dodis
Benjamin Dörr
David Doty
Petros Drineas
Devdatt Dubhashi
Vida Dujmovic
Steph Durocher
Ze'ev Dvir
Cynthia Dwork
Martin Dyer
Friedrich Eisenbrand
Khaled Elbassioni
Michael Elkin
Edith Elkind
Nadia El-Mabrouk
Robert Elsaesser
Yuval Emek
Alina Ene
Matthias Englert
Leah Epstein
Jeff Erickson
Thomas Erlebach
Bruno Escoffier
Eyal Even-Dar
Alex Fabrikant
Maryam Fazel
Sandor Fekete
Jon Feldman
Moran Feldman
Paolo Ferragina
Amos Fiat
Irene Finocchi
Samuel Fiorini
Philippe Flajolet
Abraham Flaxman
Tamas Fleiner
Lisa Fleischer
Fedor Fomin
Ehud Friedgut
Tobias Friedrich
Alan Frieze
Takuro Fukunaga
Martin Furer
Eli Gafni
Martin Gairing
Steven Galbraith
David Gamarnik
Iftach Gamzu
Sumit Ganguly
Jason Z. Gao
Jie Gao
Bernd Gärtner
Bill Gasarch
Leszek Gasieniec
Dmitry Gavinsky
Arpita Ghosh
Sharad Goel
Andreas Goerdt
Peter Golovach
Michael T. Goodrich
Parikshit Gopalan
Vineet Goyal
Ron Graham
Fabrizio Grandoni
Martin Grohe
Venkatesan Guruswami
Mohammad Taghi Hajiaghayi
Magnús Halldórsson
Thomas Dueholm Hansen
Sariel Har-Peled
Aram Harrow
Jason Hartline
Nick Harvey
Johan Hastad
Hamed Hatami
Thomas P. Hayes
Elad Hazan
Fei He
Brent Heeringa
Pavol Hell
Lisa Hellerstein
Danny Hermelin
John Herschberger
Martin Höfer |
Thomas Holenstein
Alexander Holroyd
Seokhee Hong
Peter Hoyer
Xiaoming Huo
Yumei Huo
John Iacono
Nicole Immorlica
Hiro Ito
Gabor Ivanyos
Kazuo Iwama
Mark Iwen
Markus Jalsenius
T. S. Jayram
Mark Jerrum
Tao Jiang
David Johnson
Marcin Jurdziński
Naonori Kakimura
Marcin Kamiński
Naoyuki Kamiyama
Iyad Kanj
Sampath Kannan
Ming-Yang Kao
Haim Kaplan
Sanjiv Kapoor
Bruce Kapron
Howard Karloff
Zohar Karnin
Neeraj Kayal
Peter Keevash
Jon Kelner
Julia Kempe
Sanjeev Khanna
Subhash Khot
Guy Kindler
Tamas Kiraly
David Kirkpatrick
Marcos Kiwi
Andreas Klappenecker
Phil Klein
Robert Kleinberg
Yusuke Kobayashi
Phokion Kolaitis
Alexandra Kolla
Daphne Koller
Petr Kolman
Vladimir Kolmogorov
Swastik Kopparty
Amos Korman
Guy Kortsarz
Nitish Korula
Ioannis Koutis
Matjaz Kovse
Marcin Kozik
Daniel Kral
Jan Kratochvil
Stephan Kreutzer
Ravishankar Krishnaswamy
Michael Krivelevich
Clyde Kruskal
Piotr Krysta
Fabian Kuhn
Alexander Kulikov
Abhinav Kumar
Amit Kumar
Ravi Kumar
Jan Kyncl
Oded Lachish
Stefan Langerman
Kasper Dalgaard Larsen
Silvio Lattanzi
Lap Chi Lau
Ron Lavi
Daniel Lazard
Homin Lee
James R. Lee
Troy Lee
Marc Lelarge
Renato Paes Leme
Stefano Leonardi
Jure Leskovec
Asaf Levin
Liane Lewin-Eytan
Jian Li
Ping Li
Xiangrong Li
Yi Li
Thomas Liebling
Yury Lifshits
Katrina Ligett
Andrzej Lingas
Nathan Linial
Yang Liu
Zhenming Liu
Thomas Locher
Maarten Löffler
Alex López-Ortiz
Zvi Lotker
Shachar Lovett
Brendan Lucier
Feng Luo
Bin Ma
Anthony Macula
Mohammad Mahdian
Konstantin Makarychev
Yury Makarychev
Kazuhisa Makino
David Malec
Azarakhsh Malekian
Dahlia Malkhi
David Manlove
Bodo Manthey
Alberto Marchetti-Spaccamela
Conrado Martínez
Daniel Marx
Claire Mathieu
Jiri Matousek
Michael McAllister
Ross McConnell
Lyle McGeoch
Andrew McGregor
Aranyak Mehta
Kurt Melhorn
Manor Mendel
Adam Meyerson
Olgica Milenkovic
Victor Milenkovic
Peter Bro Miltersen
Sarah Miracle
Vahab Mirrokni
Joe Mitchell
Bojan Mohar
Andrea Montanari
Ashley Montanaro
Cristopher Moore
Teo Mora
Thomas Moscibroda
Benjamin Moseley
Elchanan Mossel
David Mount
Ahuva Mu'Alem
Dhruv Mubayi
Wolfgang Mulzer
Kamesh Munagala
S. Muthukrishnan
Kiyohito Nagano
Viswanath Nagarajan
Assaf Naor
Hariharan Narayanan
Jelani Nelson
Igor Netto
Alantha Newman
Evdokia Nikolova
Todd Niven
Martin Nöllenburg
Marc Noy
Zeev Nutov
Yoshio Okamoto
Svetlana Olonetsky
Krzysztof Onak
Derek Osthus
Rafail Ostrovsky
Shayan Oveis Gharan
Martin Pàl
Alessandro Panconesi
Debmalya Panigrahi
David Parkes
Boaz Patt-Shamir
Mohan Paturi
Chris Peikert
Andrej Pelc
David Peleg
Robin Pemantle
Yuval Peres
Seth Pettie
Florian Pfender
Cindy Phillips
David Phillips
Marcin Pilipczuk
Wojciech Plandowski
Sheung-Hung Poon
Mihai Pop
Ely Porat
Eric Price
Ariel Procaccia
Kirk Pruhs
Pavel Pudlak
Jakub Radoszewski
Rajmohan Rajaraman
Alexander Rakhlin
Vijaya Ramachandran
Rajiv Raman
Venkatesh Raman
Sofya Raskhodnikova
Dieter Rautenbach
R. Ravi |
Dror Rawitz
Igor Razgon
Oded Regev
John Reif
Dustin Reishus
Thomas Richardson
Liam Roditty
Martin Roetteler
Phillip Rogaway
Heiko Röglin
Dana Ron
Adi Rosén
Peter Rossmanith
Günter Rote
Aaron Roth
Guy Rothblum
Thomas Rothvoß
Tim Roughgarden
Sambuddha Roy
Andrzej Rucinski
Mark Rudelson
Atri Rudra
Milan Ruzic
Wojciech Rytter
Kunihiko Sadakane
Bardia Sadri
Barna Saha
Saurabh Saket
Michael Saks
Mahyar Salek
Mark Sandler
Piotr Sankowski
Miklos Santha
Raman Sanyal
Shubhangi Saraf
Tamas Sarlos
Thomas Sauerwald
Rahul Savani
Nitin Saxena
Guido Schäfer
Michael Schapira
Christian Scheideler
Sven Schewe
Grant Schoenenbeck
Uwe Schoning
Warren Schudy
Andreas Schulz
Andrea Schumm
Roy Schwartz
Michael Schwarz
Robert Schweller
Bob Sedgewick
Michael Segal
Danny Segev
Pranab Sen
Siddhartha Sen
C. Seshadhri
Hadas Shachnai
Micha Sharir
Aneesh Sharma
Vikram Sharma
Don Sheehy
Bruce Shepherd
Xiaolin Shi
Akiyoshi Shioura
Hang Si
Anastasios Sidiropoulos
Somnath Sikdar
Joe Simons
Alistair Sinclair
Yaron Singer
Mohit Singh
Balasubramanian Sivan
Steve Skiena
Danny Sleator
Michiel Smid
Marie Snipes
Anthony Man-Cho So
Christian Sohler
David Soloveichik
Christian Sommer
Troels Sørensen
Alexander Souza
Joel Spencer
Daniel Spielman
Paul Spirakis
Joachim Spoerhase
Karthik Sridharan
Aravind Srinivasan
Srikanth Srinivasan
Venkatesh Srinivasan
Nikhil Srivastava
Dudley Stark
Damien Stehlè
Cliff Stein
Aaron Sterling
David Steurer
Leen Stougie
Darren Strash
Martin Strauss
Subhash Suri
Maxim Sviridenko
Zoya Svitkina
Chaitanya Swamy
Tibor Szabo
Tsz Wo Sze
Kenjiro Takazawa
Kunal Talwar
Hisao Tamaki
Akihisa Tamura
Terry Tao
Eva Tardos
Siamak Tazari
Moshe Tennenholtz
Prasad Tetali
Mikkel Thorup
Takeshi Tokuyama
Laura Toma
Jacobo Toran
Eric Torng
Ann Trenk
Luca Trevisan
Joel Tropp
Nicolas Trotignon
Lowell Trott
Madhur Tulsiani
Mark Tygert
Ryuuhei Uehara
Christopher Umans
Yushi Uno
Vinod Vaikuntanathan
Gregory Valiant
Leslie Valiant
Paul Valiant
Rob van Stee
Kasturi Varadarajan
Virginia Vassilevska Williams
Santosh Vempala
Suresh Venkatasubramanian
Elad Verbin
Roman Vershynin
Antoine Vigneron
Eric Vigoda
Dan Vilenchik
Uzi Vishkin
Nisheeth Vishnoi
Berthold Vöcking
Ilya Volkovich
Jan Vondrak
Sergei Vorobyov
Thuc Vu
Yajun Wang
Yihui Wang
Tandy Warnow
Hoeteck Wee
Zhewei Wei
Udi Weider
Oren Weimann
Carola Wenk
Matthias Westermann
Tom Wexler
Udi Wieder
Christian Wieschebrink
Gordon Wilfong
Chris Wilkens
Ryan Williams
David Williamson
James Wilson
Karl Wimmer
Peter Winkler
Gerhard Wöeginger
Paul Wollan
Prudence Wong
David Woodruff
Mary Wootters
Jenn Wortman Vaughan
Yi Wu
Christian Wulff-Nilsen
Lirong Xia
Zenglin Xu
Maki Yamamoto
Qiqi Yan
Jonathan Yaniv
Mihalis Yannakakis
Chee Yap
Deshi Ye
Sergey Yekhanin
Ke Yi
Yuichi Yoshida
Neal Young
Maxwell Young
Raphael Yuster
Rico Zenklusen
Guochuan Zhang
Qin Zhang
Shengyu Zhang
Hairong Zhao |