Preface and Acknowledgements

The papers in this volume were presented at the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, held January 17-19, 2012 in Kyoto, Japan. 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 138 submissions of the 517 that were submitted. By the early registration deadline, 597 abstracts were registered, resulting in 523 full paper submissions, 6 of which were later withdrawn by the authors. Papers were chosen based on originality, technical contribution, and relevance. The committee was helped immensely in this process by reports from over 650 external reviewers. We are very grateful to them for their help.

The submissions were not formally refereed, although a sincere attempt was made to verify the main claims and to provide some feedback to authors. It is expected that most of the accepted papers will appear subsequently (possibly in more complete form) in peer-reviewed scientific journals.

The program committee chose the paper
Computing All Maps into a Sphere
by Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner,
for the Best Paper award.

The paper
Near Linear Time $\oeps$-approximation for Restricted Shortest Paths in Undirected Graphs
by Aaron Bernstein,
was chosen for the Best Student Paper award.

Two speakers were invited to give plenary talks at the conference: Jennifer Chayes and Martin Grohe.

The program committee thanks all the authors for supporting the conference through their submissions. I would like to thank the program committee members for their dedication to review and discuss the submissions. I thank the steering committee members Moses Charikar, David Johnson, Claire Mathieu, Mike Molloy, and Prasad Tetali, and SODA 2011 PC chair Dana Randall for indispensable advice. I also thank Kirsten Wilden, Linda Thiel, and other members of the SIAM staff for their help.

Yuval Rabani SODA 2012 Program Committee chair

SODA 2012 Program Committee

Program Committee Chair
Yuval Rabani, The Hebrew University of Jerusalem, Israel

Local Conference Organizers
Kazuo Iwama, Kyoto University, Japan Kenichi Kawarabayashi, National Institute of Informatics, Japan

Program Committee
Nikhil Bansal, IBM T.J. Watson Research Center, USA
Gruia Calinescu, Illinois Institute of Technology, USA
Chandra Chekuri, University of Illinois, Urbana-Champaign, USA
Nikhil Devanur, Microsoft Research, Redmond, USA
Funda Ergun, Simon Fraser University, Canada
Uriel Feige, The Weizmann Institute, Israel
Irene Finocchi, University of Rome "La Sapienza," Italy
Fabrizio Grandoni, Università di Roma Tor Vergata, Italy
Howard Karloff, AT&T Labs - Research, USA
Jonathan Kelner, Massachusetts Institute of Technology, USA
Daniel Kral, Charles University Prague, Czech Republic
Daniela Kuhn, Birmingham University, United Kingdom
Nati Linial, The Hebrew University of Jerusalem, Israel
Anna Lubiw, University of Waterloo, Canada
Bojan Mohar, Simon Fraser University, Canada, and University of Ljubljana, Slovenia
Petra Mutzel, Technische Universität Dortmund, Germany
Ryan O'Donnell, Carnegie Mellon University, USA
Daniel Panario, Carleton University, Canada
Rina Panigrahy, Microsoft Research Silicon Valley, USA
Satish Rao, University of California, Berkeley, USA
Andrea Richa, Arizona State University, USA
Jared Saia, University of New Mexico, USA
Anastasios Sidiropoulos, Toyota Technological Institute at Chicago, USA
Christian Sohler, Technische Universität Dortmund, Germany
Aravind Srinivasan, University of Maryland, College Park, USA
David Steurer, Microsoft Research New England, USA
Mikkel Thorup, University of Copenhagen, Denmark and AT&T Labs – Research, USA
Sergei Vassilvitskii, Yahoo! Research, USA
Jan Vondrak, IBM Almaden Research Center, USA
Ryan Williams, IBM Almaden Research Center, USA
David Woodruff, IBM Almaden Research Center, USA

Steering Committee
Moses Charikar, Princeton University, USA
David Johnson, AT&T Labs – Research, USA
Claire Mathieu, Brown University, USA
Mike Molloy, University of Toronto, Canada
Prasad Tetali, Georgia Institute of Technology, USA

Acknowledgments

The program committee thanks the following colleagues who generously gave their help and time to read the review SODA 2012 submissions.

Scott Aaronson
Amirali Abdullah
Zachary Abel
Ittai Abraham
Dimitris Achlioptas
Louigi Addario-Berry
Peyman Afshani
Vaneet Aggarwal
Nir Ailon
Ali Akhavi
Soroush Alamdari
Susanne Albers
Abdo Alfakih
Noga Alon
Nina Amenta
Alexandr Andoni
Matthew Andrews
Elliot Anshelevich
Joerg Arndt
Sanjeev Arora
James Aspnes
Yossi Azar
Moshe Babaioff
Ashwinkumar Badanidiyuru
Antar Bandyopadhyay
Siddharth Barman
Libor Barto
Frederique Bassino
Surender Baswana
Mohammadhossein Bateni
Tugkan Batu
Ulrich Bauer
Mohsen Bayati
Rida Bazzi
Mihir Bellare
Michael Ben Or
Eli Ben-Sasson
Petra Berenbrink
Andre Berger
Piotr Berman
Aaron Bernstein
Stephane Bessi
Anand Bhalgat
Umang Bhaskar
Binay Bhattacharya
Kshipra Bhawalkar
Therese Biedl
Marcin Bienkowski
Benjamin Birnbaum
Andreas Björklund
Avrim Blum
Johannes Blömer
Beate Bollig
Nicolas Bonichon
Vincenzo Bonifaci
Claudson Bornstein
Glencora Borradaile
Glencora Borradaille
Sylvia Boyd
Franz Brandenburg
Andreas Brandstadt
Peter Brass
Patrick Briest
Gerth Stølting Brodal
Joshua Brody
Hajo Broersma
Vaclav Brozek
Sebastien Bubeck
Niv Buchbinder
Harry Buhrman
Andrei Bulatov
Jonathan Buss
Jaroslaw Byrka
Sergio Cabello
Tiziana Calamoneri
Saverio Caminiti
Alberto Caprara
Ioannis Caragiannis
Jean Cardinal
Ruggiero Cavallo
Elisa Celis
Amit Chakrabarti
Deeparnab Chakrabarty
Parinya Chalermsook
Erin Chambers
Ho-Leung Chan
Siu On Chan
Timothy M. Chan
Harish Chandran
Guillaume Chapuy
Bernard Chazelle
Chao Chen
Ho-Lin Chen
Ning Chen
Xi Chen
Christine Cheng
Kevin Cheung
Flavio Chierichetti
Andrew Childs
Eden Chlamtac
Julia Chuzhoy
Ferdinando Cicalese
Sebastian Cioba
Ken Clarkson
Peter Clote
Julien Clément
Paolo Codenotti
Amin Coja-Oghlan
Richard Cole
Éric Colin De Verdière
Michele Conforti
Oliver Cooley
Graham Cormode
Maxime Crochemore
Mary Cryan
Bela Csaba
Bill Cunningham
Marek Cygan
Artur Czumaj
Ivan Damgård
Mirela Damian
Varsha Dani
Atish Das Sarma
Anirban Dasgupta
Sanjoy Dasgupta
Constantinos Daskalakis
Sven De Vries
Brian Dean
Damian Dechev
Holger Dell
Daniel Delling
Erik D. Demaine
Camil Demetrescu
Narsingh Deo
Luc Devroye
Persi Diaconis
Giuseppe Di Battista
Martin Dietzfelbinger
Dimitrios I. Diochnos
John Dixon
Shahar Dobzinski
Benjamin Doerr
Feodor Dragan
Stefan Droste
Andrew Drucker
Devdatt Dubhashi
Shaddin Dughmi
Vida Dujomovic
Zdenek Dvorak
Alon Efrat
Michael Elkin
Alina Ene
Matthias Englert
David Eppstein
Leah Epstein
Jeff Erickson
Thomas Erlebach
Esther Ezra
Dvir Falik
Toni Farley
Sandor Fekete
Dan Feldman
Jon Feldman
Vitaly Feldman
Stefan Felsner
Cristina Fernandes
Yaacov Fernandess
Umberto Ferraro Petrillo
Efi Fogel
Fedor V. Fomin
Nikolaos Fountoulakis
Mahmoud Fouz
Gianni Franceschini
Tom Friedetzky
Alan Frieze
Matteo Frigo
Hu Fu
Stefan Funke
Emanuele Guido Fusco
Eric Fusy
Martin Fürer
Harold Gabow
Martin Gairing
Steven Galbraith
Nicola Galesi
Jane Gao
Jason Gao
Jie Gao
Naveen Garg
Serge Gaspers
Tomas Gavenciak
Rong Ge
Dan Geiger
Stefanie Gerke
Arijit Ghosh
Joachim Giesen
Anna Gilbert
Marc Gille
Bernhard Gittenberger
Marc Glisse
Gagan Goel
Sharad Goel
Michel Goemans
Leslie Ann Goldberg
Michael Goodrich
Parikshit Gopalan
Ian Goulden
Navin Goyal
Vineet Goyal
Gero Greiner
Martin Grohe
Martin Gronemann
Oktay Gunluk
Anupam Gupta
Venkatesan Guruswami
Dan Gusfield
Gregory Gutin
Shai Gutner
Carsten Gutwenger
Bernhard Haeupler
Mohammadtaghi Hajiaghayi
Iman Hajirasouliha
Sean Hallgren
Sariel Har-Peled
Moritz Hardt
Jason Hartline
Nicholas Harvey
Nick Harvey

Avinatan Hassidim
Mathias Hauptmann
Thomas Hayes
Tom Hayes
Elad Hazan
Dan Hefetz
Frank Hellweg
Nadia Heninger
Mark Herbster
Danny Hermelin
Klaus Hildebrandt
Jan Hladky
Petr Hlineny
Alexander Holroyd
Wing-Kai Hon
Tsan-Sheng Hsu
Chien-Chung Huang
Zhiyi Huang
Benoît Hudson
Alexander Hulpke
Hsien-Kuei Hwang
Sungjin Im
Nicole Immorlica
Piotr Indyk
R. Inkulu
Giuseppe F. Italiano
Kazuo Iwama
Riko Jacob
Sina Jafarpour
Kamal Jain
Andreas Jakoby
Esaias J Janse Van Rensburg
Klaus Jansen
Vít Jelínek
Mark Jerrum
Madhav Jha
Patrick Jordan
Tibor Jordan
Hossein Jowhari
Jeff Kahn
Gil Kalai
Satyen Kale
Frank Kammer
Panagiotis Kanellopoulos
Ross J. Kang
Yashodhan Kanoria
Ming-Yang Kao
Haim Kaplan
Sanjiv Kapoor
Michael Kapralov
Anna Karlin
Jonathan Katz
Telikepalli Kavitha
Akitoshi Kawamura
Ken-Ichi Kawarabayashi
Neeraj Kayal
Iordanis Kerenidis
Rohit Khandekar
Sanjeev Khanna
Ilhee Kim
Valerie King
Lefteris Kirousis
Marcos Kiwi
Pavel Klavík
Karsten Klein
Rolf Klein
Robert Kleinberg
Adam Klivans
Ton Kloks
Christian Knauer
Fiachra Knox
Yusuke Kobayashi
Jochen Koenemann
Petr Kolman
Swastik Kopparty
Guy Kortsarz
Nitish Korula
Ioannis Koutis
Yiannis Koutis
Lukasz Kowalik
Dariusz Kowalski
Samory Kpotufe
Jan Kratochvil
Stefan Kratsch
Hugo Krawczyk
Marek Krcal
Stephan Kreutzer
Nils Kriege
Ravishankar Krishnaswamy
Andrei Krokhin
Ted Krovetz
Hari Krovi
Fabian Kuhn
Amit Kumar
Ravi Kumar
Ranjit Kumaresan
Jan Kyncl
Oded Lachish
Sebastien Lahaie
Sebastien Lahie
Christiane Lammersen
Stefan Langerman
Silvio Lattanzi
Lap Chi Lau
Luigi Laura
Sylvain Lazard
Francis Lazarus
James Lee
Marc Lelarge
Stefano Leonardi
David Letscher
Benjamin Leveque
Moshe Lewenstein
Thomas Lewiner
Jian Li
Ming Li
Minming Li
Yi Li
David Liben-Nowell
Bernard Lidicky
Frauke Liers
Katrina Ligett
Allan Lo
Ilan Lobel
Po-Shen Loh
Daniel Lokshtanov
Alejandro Lopez-Ortiz
Brendan Lucier
Gabor Lugosi
Bin Ma
Raphael Machado
Ashwin Machanavajjhala
Aleksander Madry
Frederic Maffray
Anil Maheshwari
Yury Makarychev
Martin Malandro
David Malec
Dahlia Malkhi
Ion Mandoiu
David Manlove
Yishay Mansour
Virendra Marathe
Conrado Martinez
Dániel Marx
Claire Mathieu
Jiri Matousek
Kevin Matulef
Colin Mcdiarmid
Andrew Mcgregor
Andrew Mclennan
Abbas Mehrabian
Aranyak Mehta
Ruta Mehta
Raghu Meka
David Meyer
Daniele Micciancio
Preda Mihailescu
Peter Bro Miltersen
Vahab Mirrokni
Marni Mishna
Joseph Mitchell
Michael Molloy
Ankur Moitra
Michael Molloy
Morteza Monemizadeh
Ravi Montenegro
Cristopher Moore
Marc Moreno Maza
Pat Morin
Ben Morris
Benjamin Moseley
Robin Moser
Dana Moshkovitz
Elchanan Mossel
Herve Moulin
David Mount
Bernard Mourrain
Kamesh Munagala
Alexander Munteanu
S. Muthukrishnan
Richard Mycroft
Daniel Müllner
Uri Nadav
Philippe Nadeau
Viswanath Nagarajan
Assaf Naor
Moni Naor
Seffi Naor
Gonzalo Navarro
Ashwin Nayak
Amir Nayyeri
Jesper Nederlof
Yakov Nekrich
Jelani Nelson
Ilan Newman
Thach Nguyen
Thanh Nguyen
Rolf Niedermeier
Martin Niemeier
Vlado Nikiforov
Naomi Nishimura
Igor Nitto
Gabriel Nivasch
Sergey Norin
Serguei Norine
Isabella Novik
Joseph O'Rourke
Jan Obdrzalek
Olga Ohrimenko
Yoshio Okamoto
Krzysztof Onak
Deryk Osthus
Steve Oudot
Shayan Oveis Gharan
Maks Ovsjanikov
Rasmus Pagh
Konstantinos Panagiotou
Gopal Pandurangan
Ondrej Pangrac
Alois Panholzer
Debmalya Panigrahi
Gregor Pardella
Jongsoo Park
Pavel Patak
Amit Patel
Vinayak Pathak
Mihai Patrascu

Soumya Paul
Chris Peikert
Andrzej Pelc
Michael Pelsmajer
Rudi Pendavingh
Jeff Phillips
Diana Piguet
Georgios Piliouras
Benny Pinkas
Solon P. Pissis
Boris Pittel
Preyas Popat
Ely Porat
Manoj Prabhakaran
Pawel Pralat
Bart Preneel
Ariel Procaccia
Guido Proietti
Kirk Pruhs
Luis Rademacher
Prasad Raghavendra
Rajmohan Rajaraman
Vijaya Ramachandran
Rajeev Raman
Dana Randall
Bert Randerath
Sofya Raskhodnikova
Alexander Razborov
Igor Razgon
Oded Regev
Oliver Riordan
Igor Rivin
Sebastien Roch
Daniel Rockmore
Liam Roditty
Dana Ron
Adi Rosen
Elissa Ross
Günter Rote
Aaron Roth
Guy Rothblum
Thomas Rothvoss
Tim Roughgarden
Marie-Francoise Roy
Atri Rudra
Frank Ruskey
Alexander Russell
Harald Räcke
Domenico Sacca'
Sushant Sachdeva
Mert Saglam
Barna Saha
S. Cenk Sahinalp
Michael Saks
Mike Saks
Amin Sakzad
Mohammad Salavatipour
Mahyar Salek
Robert Samal
Peter Sanders
Piotr Sankowski
Rahul Santhanam
Ignasi Sau
Thomas Sauerwald
Saket Saurabh
Nitin Saxena
Mathias Schacht
Guido Schaefer
Marcus Schaefer
Michael Schapira
Christian Scheideler
Renate Scheidler
Ingo Schiermeyer
Stefan Schmid
Melanie Schmidt
Warren Schudy
Andreas S. Schulz
Robert Schweller
Chris Schwiegelshohn
Eric Sedgwick
Michael Segal
Gil Segev
Sandeep Sen
Siddhartha Sen
Akos Seress
Rocco Servedio
C. Seshadhri
Jirí Sgall
Aneesh Sharma
Micha Sharir
Bruce Shepherd
Jonah Sherman
Igor Shparlinski
Francesco Silvestri
Blerina Sinaimeri
Alistair Sinclair
Yaron Singer
Mohit Singh
Amitabh Sinha
Rakesh Sinha
Ali Sinop
Balasubramanian Sivan
Alexander Skopalik
Primoz Skraba
Martin Skutella
Aleksandrs Slivkins
Allan Sly
Adam Smith
Sagi Snir
Christian Sommer
Jonathan Sorenson
Robert Spalek
Daniel Spielman
Paul Spirakis
Joachim Spoerhase
Reto Spöhel
Nikhil Srivastava
Martijn Stam
Daniel Stefankovic
Damien Stehle
Benjamin Steinberg
Aaron Sterling
Martin Strauss
Ondrej Suchy
Xiaoming Sun
Mukund Sundararajan
Jukka Suomela
Siddharth Suri
Ola Svensson
Maxim Sviridenko
Zoya Svitkina
Chaitanya Swamy
Mario Szegedy
Kunal Talwar
Li-Yang Tan
Xuehou Tan
Martin Tancer
Anusch Taraz
Eva Tardos
Gabor Tardos
Siamak Tazari
Shang-Hua Teng
Stefano Tessaro
Prasad Tetali
Ambuj Tewari
Johan Thapper
Dimitrios Thilikos
Robin Thomas
Takeshi Tokuyama
Andrew Treglown
Amitabh Trehan
Pushkar Tripathi
Elias Tsigaridas
Madhur Tulsiani
Torsten Ueckerdt
Marc Uetz
Nelson Uhan
Chris Umans
Jan Vahrenhold
Gregory Valiant
Paul Valiant
Brigitte Vallee
Wim Van Dam
Erik Jan Van Leeuwen
Kasturi Varadarajan
Virginia Vassilevska Williams
Martin Vatshelle
Andrea Vattani
Erik Vee
Santosh S. Vempala
Rossano Venturini
Elad Verbin
Adrian Vetta
Angelina Vidali
Thomas Vidick
Eric Vigoda
Aravindan Vijayaraghavan
Danny Vilenchik
Tomas Vinar
Alfredo Viola
Sundar Vishwanathan
Berthold Voecking
Van Vu
Anil Vullikanti
Kristina Vuskovic
Jens Vygen
Uli Wagner
Christophe Weibel
Oren Weimann
Omer Weissbrod
Carola Wenk
Renato Werneck
Udi Wieder
Ryan Williams
David Wilson
James Wilson
Peter Winkler
Gerhard J. Woeginger
Philipp Woelfel
Dominik Wojtczak
Maverick Woo
David R. Wood
Yi Wu
Christian Wulff- Nilsen
Donglin Xia
David Xiao
Qiqi Yan
Mihalis Yannakakis
Grigory Yaroslavtsev
Sergey Yekhanin
Yuichi Yoshida
Maxwell Young
Neal Young
Xingxing Yu
Raphael Yuster
Mariette Yvinec
Morteza Zadimoghaddam
Norbert Zeh
Rico Zenklusen
Bernd Zey
Qin Zhang
Shengyu Zhang
Xia Zhou
Yuan Zhou
Binhai Zhu
Anastasios Zouzias
Uri Zwick
Yori Zwols