39th International Colloquium on Automata, Languages and Programming (ICALP 2012)

Invited Talks
- Gilles Dowek: A Theory Independent Curry-De Bruijn-Howard Correspondence Kohei Honda Session Types and Distributed Computing
- Stefano Leonardi: On Multiple Keyword Sponsored Search Auctions with Budgets
- Daniel A. Spielman: Algorithms, Graph Theory, and the Solution of Laplacian Linear Equation
- Berthold Vöcking: Randomised Mechanisms for Multi-Unit Auctions
- Alan Turing talk: David Harel Standing on the Shoulders of a Giant: One Person’s Experience of Turing’s Impact

Contributed Talks
- Inge Li Gørtz, Viswanath Nagarajan and Rishi Saket: Stochastic Vehicle Routing with Recourse
- Nicole Megow, Martin Skutella, Jose Verschae and Andreas Wiese: The Power of Recourse for Online MST and TSP
- Yossi Azar and Iftah Gamzu Efficient Submodular: Function Maximization under Linear Packing Constraints
- Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese: Assigning Sporadic Tasks to Unrelated Parallel Machines
- Siddharth Barman, Shuchi Chawla, David Malec and Seeun Umboh: Secretary Problems with Convex Costs
- Ning Chen, Xiaotie Deng, Hongyang Zhang and Jie Zhang: Incentive Ratios of Fisher Markets
- Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos and Yaron Singer: Efficiency-Revenue Trade-offs in Auctions
- Khaled Elbassioni: A QPTAS for -Envy-Free Profit-Maximizing Pricing on Line Graphs
- Elias Koutsoupias and Katia Papakonstantinopoulou: Contention Issues in Congestion Games
- Fedor Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk: Minimizing Rosenthal Potential in Multicast Games
- Albert Atserias and Anuj Dawar: Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers
- Anuj Dawar and Bjarki Holm: Pebble Games with Algebraic Rules
- John Fearnley and Sven Schewe: Time and Parallelizability Results for Parity Games with Bounded Treewidth
- Manfred Kufleitner and Alexander Lauser: Lattices of Logical Fragments over Words
- Tomáš Gavenčiak, Daniel Kral and Sang-Il Oum: Deciding First Order Logic Properties of Matroids
- Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung CRAM: Compressed Random Access Memory
- Yuval Emek, Magnus M. Halldorsson and Adi Rosen: Space-Constrained Interval Selection
- Artur Jeż: Faster Fully Compressed Pattern Matching by Recompression
- Karl Bringmann and Konstantinos Panagiotou: Efficient Sampling Methods for Discrete Distributions
- László Babai, Paolo Codenotti and Youming Qiao: Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups
- Lukas Polacek and Ola Svensson: Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
- Andrew Hughes, A Pavan, Nathan Russell and Alan Selman: A Thirty Year Old Conjecture about Promise Problems
- Hiro Ito, Shin-Ichi Tanigawa and Yuichi Yoshida: Constant-Time Algorithms for Sparsity Matroids
- Maribel Fernandez and Albert Rubio: Nominal Completion for Rewrite Systems with Binders
- Mikołaj Bojańczyk and Thomas Place: Toward Model Theory with Data Values
- Mikołaj Bojańczyk and Sławomir Lasota: A Machine-Independent Characterization of Timed Languages
- Andrzej Murawski and Nikos Tzevelekos: Algorithmic Games for Full Ground References
- Leslie Ann Goldberg and Mark Jerrum: The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)
- Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter: Regular Languages are Church-Rosser Congruential
- Piotr Krysta and Berthold Vöcking: Online Mechanism Design (Randomized Rounding on the Fly)

July 10
- Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Magnus Wahlstrom: Clique cover and graph separation: New incompressibility results
- Bingkai Lin and Yijia Chen: The Parameterized Complexity of k-edge Induced Subgraphs
- Rajesh Chitnis, Marek Cygan, Mohammadtaghi Hajiaghayi and Dániel Marx: Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
- Michael Fellows, Ariel Kulik, Frances Rosamond and Hadas Shachnai: Parameterized Approximation via Fidelity Preserving Transformations
- Rahul Santhanam and Srikanth Srinivasan: On the Limits of Sparsification
- Joshua Baron, Rafail Ostrovsky and Ivan Visconti: Nearly Simultaneously Resettable Black-Box Zero Knowledge
- Michael Rabin, Yishay Mansour, Muthu Muthuikrishnan and Moti Yung: Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
- Justin Thaler, Jonathan Ullman and Salil Vadhan: Faster Algorithms for Privately Releasing Marginals
- Anastasios Zouzias: A Matrix Hyperbolic Cosine Algorithm and Applications
- Amit Deshpande, Ravindran Kannan and Nikhil Srivastava: Zero-One Rounding of Singular Vectors
- Yaron Velner: The Complexity of Mean-Payoff Automaton Expression
- Gilles Dowek and Pablo Arrighi: Causal Graph Dynamics
- Patricia Bouyer, Nicolas Markey and Ocan Sankur: Robust Reachability in Timed Automata: A Game-based Approach
- Hongfei Fu: Computing Game Metrics on Markov Decision Processes
- Tomas Brazdil, Antonin Kucera, Petr Novotný and Dominik Wojtczak: Minimizing Expected Termination Time in One-Counter Markov Decision Processes
- Michael Kapralov and Rina Panigrahy: NNS Lower Bounds via Metric Expansion for and EMD
- T-H. Hubert Chan, Mingfei Li and Li Ning: Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
- Danny Z. Chen and Haitao Wang: Computing the Visibility Polygon of an Island in a Polygonal Domain
- Jens M. Schmidt: Certifying 3-Connectivitiy in Linear Time
- Pushkar Tripathi, Prasad Tetali and Kevin Costello: Stochastic Matching with Commitment
- Loukas Georgiadis and Robert Tarjan: Dominators, Directed Bipolar Orders, and Independent Spanning Trees
- Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald and He Sun: Counting Arbitrary Subgraphs in Data Streams
- Marcel Ochel, Klaus Radke and Berthold Vöcking: Online Packing with Gradually Improving Capacity Estimations with Applications to Network Lifetime Maximization
- Michael Goodrich and Michael Mitzenmacher: Anonymous Card Shuffling and its Applications to Parallel Mixnets

July 11
- Elad Verbin and Qin Zhang Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
- Maria Florina Balcan and Yingyu Liang: Clustering under Perturbation Resilience
- Justin Hsu, Sanjeev Khanna and Aaron Roth: Distributed Private Heavy Hitters
- Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan: Quadratic Programming with a Ratio Objective
- Kousha Etessami, Alistair Stewart and Mihalis Yannakakis: Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
- C.-H. Luke Ong and Takeshi Tsukada: Two-Level Game Semantics, Intersection Types and Recursion Schemes
- Sylvain Salvati, Giulio Manzonetto, Mai Gehrke and Henk Barendregt: Loader and Urzyczyn are Logically Related
- Chris Broadbent, Arnaud Carayol, Matthew Hague and Olivier Serre: A Saturation Method for Collapsible Pushdown Systems
- Christopher Broadbent: Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata
- Szymon Toruńczyk: Languages of Profinite Words and the Limitedness Problem
- Reuven Bar-Yehuda, Erez Kantor, Shay Kutten and Dror Rawitz: Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs
- Nishanth Chandran, Juan Garay and Rafail Ostrovsky: Edge Fault Tolerance on Sparse Networks
- Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan: k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth
- Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach and Maurizio Patrignani: Computational Complexity of Traffic Hijacking under BGP and S-BGP
- Navendu Jain, Ishai Menache, Joseph Naor and F. Bruce Shepherd: Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks

July 12
- Stacey Jeffery, Robin Kothari and Frédéric Magniez: Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
- Shelby Kimmel: Quantum Adversary (Upper) Bound
- Sevag Gharibian and Julia Kempe: Hardness of Approximation for Quantum Problems
- Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis, Dmitry Kravchenko, Raitis Ozols, Juris Smotrovs and - Madars Virza: Quantum Strategies are Better than Classical in Almost Any XOR Game
- S. Laplante, V. Lerays and J. Roland: Classical and Quantum Partition Bound and Detector Inefficiency
- Sungjin Im, Viswanath Nagarajan and Ruben Van Der Zwaan: Minimum Latency Submodular Cover
- Robert Krauthgamer and Tamar Zondiner: Preserving Terminal Distances using Minors
- Marco Molinaro and R Ravi: Geometry of Online Packing Linear Programs
- Anupam Gupta and Viswanath Nagarajan: Approximating Sparse Covering Integer Programs Online
- Bundit Laekhanukit, Shayan Oveis Gharan and Mohit Singh: An Improved Approximation Algorithm for The Minimum Size k-Arc Connected Subgraph Problem
- Luca Aceto, Arnaud Carayol, Zoltan Esik and Anna Ingolfsdottir: Algebraic Synchronization Trees and Processes
- Tadeusz Litak, Dirk Pattinson, Katsuhiko Sano and Lutz Schröder: Coalgebraic Predicate Logic
- Marcelo Fiore Discrete Generalised Polynomial Functors
- Uday Reddy and Brian Dunphy: An Automata-Theoretic Model of Idealized Algol
- Grigore Rosu and Andrei Stefanescu: Towards a Unified Theory of Operational and Axiomatic
Semantics
- Arash Farzan, Ian Munro and Rajeev Raman: Succinct Indices for Range Queries with applications to Orthogonal Range Maxima
- Prosenjit Bose, Sebastien Collette, Rolf Fagerberg and Stefan Langerman: De-amortizing Binary Search Trees
- Yaoyun Shi and Xiaodi Wu: Epsilon-net Method for Optimizations over Separable States
- Anupam Gupta and Kevin Lewi: The Online Metric Matching Problem for Doubling Metrics
- Bruno Bauwens: Complexity of Complexity and Maximal Plain versus Prefix-free Kolmogorov Complexity
- Uriel Feige and Shlomo Jozeph: Universal Factor Graphs
- Yishay Mansour, Aviad Rubinstein, Shai Vardi and Ning Xie: Converting Online Algorithms To Local Computation

Algorithms
- Michael Dinitz, Guy Kortsarz and Ran Raz: Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
- David Peleg, Liam Roditty and Elad Tal: Distributed Algorithms for Network Diameter and Girth
- Leonid Barenboim: On the Locality of NP-Complete Problems
- Andrew Berns, James Hegeman and Sriram Pemmaraju: Super-Fast Distributed Algorithms for Metric Facility Location
- Yoann Dieudonne and Andrzej Pelc: Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports

July 13
- Niv Buchbinder, Seffi Naor, R. Ravi and Mohit Singh: Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
- Moses Charikar and Shi Li: A Dependent LP-rounding Approach for the k-Median Problem
- Barna Saha and Samir Khuller: Set Cover Revisited: Hypergraph Cover with Hard Capacities
- Jaroslaw Byrka and Bartosz Rybicki: Improved LP-rounding Approximation Algorithm for k-level Uncapacitated Facility Location
- Chandra Chekuri, Alina Ene and Ali Vakilian: Node-weighted Network Design in Planar and Minor-closed Families of Graphs
- Robert Crowston, Mark Jones and Matthias Mnich: Max-Cut Parameterized Above the Edwards-Erdős Bound
- Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström: Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
- Daniel Lokshtanov and M. S. Ramanujan Parameterized: Tractability of Multiway Cut with Parity Constraints
- Dániel Marx: A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Philip Klein and Dániel Marx: Solving Planar k-Terminal Cut in √Time
- Mikołaj Bojańczyk and Thomas Place: Regular Languages of Infinite Trees that are Boolean Combinations of Open Sets
- Denis Kuperberg and Michael Vanden Boom: On the Expressive Power of Cost Logics over Infinite Words
- Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii and Michael Zakharyaschev: Exponential Lower Bounds and Separation for Query Rewriting
- Michael Benedikt, Pierre Bourhis and Pierre Senellart: Monadic Datalog Containment
Rajeev Alur and Loris D'Antoni: Streaming Tree Transducers
- Magnus M. Halldorsson, Xiaoming Sun, Mario Szegedy and Chengu Wang: Streaming and Communication Complexity of Clique Approximation
- Reut Levi, Dana Ron and Ronitt Rubinfeld: Testing Similar Means
- Deeparnab Chakrabarty and Zhiyi Huang Testing Coverage Functions
- Anil Ada, Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen: The NOF Multiparty Communication Complexity of Composed

Functions
- Serge Gaspers and Stefan Szeider: Backdoors to Acyclic SAT
- Anindya De, Ilias Diakonikolas and Rocco Servedio: The Inverse Shapley Value Problem
- Matthew Patitz, Robert Schweller, Bin Fu and Robert Sheline: Self-Assembly with Geometric Tiles
- Dimitris Achlioptas and Ricardo Menchaca-Mendez: Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method