All talks are taking place in Zeeman Building at the Warwick Mathematics Institute, University of Warwick.

Monday, July 9
8:00 – 8:45	Registration (Zeeman Building)
Session I. Room MS.02
8:45 – 9:00	Opening and Welcome
9:00 – 10:00	Invited Talk	Stefano Leonardi On Multiple Keyword Sponsored Search Auctions with Budgets
10:00 – 10:30	Coffee break
Session IIa. Track A1. Room MS.02
10:30 – 10:50	Inge Li Gørtz, Viswanath Nagarajan and Rishi Saket Stochastic Vehicle Routing with Recourse
10:55 – 11:15	Nicole Megow, Martin Skutella, Jose Verschae and Andreas Wiese The Power of Recourse for Online MST and TSP
11:20 – 11:40	Yossi Azar and Iftah Gamzu Efficient Submodular Function Maximization under Linear Packing Constraints
11:45 – 12:05	Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese Assigning Sporadic Tasks to Unrelated Parallel Machines
12:10 – 12:30	Siddharth Barman, Shuchi Chawla, David Malec and Seeun Umboh Secretary Problems with Convex Costs
Session IIb. Track C1. Room MS.01
10:30 – 10:50	Ning Chen, Xiaotie Deng, Hongyang Zhang and Jie Zhang Incentive Ratios of Fisher Markets
10:55 – 11:15	Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos and Yaron Singer Efficiency-Revenue Trade-offs in Auctions
11:20 – 11:40	Khaled Elbassioni A QPTAS for ε-Envy-Free Profit-Maximizing Pricing on Line Graphs
11:45 – 12:05	Elias Koutsoupias and Katia Papakonstantinopoulou Contention Issues in Congestion Games
12:10 – 12:30	Fedor Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk Minimizing Rosenthal Potential in Multicast Games
Session IIc. Track B1. Room MS.05
10:30 – 10:50	Albert Atserias and Anuj Dawar Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers
10:55 – 11:15	Anuj Dawar and Bjarki Holm Pebble Games with Algebraic Rules
11:20 – 11:40	John Fearnley and Sven Schewe Time and Parallelizability Results for Parity Games with Bounded Treewidth
11:45 – 12:05	Manfred Kufleitner and Alexander Lauser Lattices of Logical Fragments over Words
12:10 – 12:30	Tomáš Gavenčiak, Daniel Kral and Sang-Il Oum Deciding First Order Logic Properties of Matroids
12:45 – 14:00	Lunch (Rootes Building)
Session IIIa. Track A2. Room MS.02
14:10 – 14:30	Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung CRAM: Compressed Random Access Memory
14:35 – 14:55	Yuval Emek, Magnus M. Halldorsson and Adi Rosen Space-Constrained Interval Selection
15:00 – 15:20	Artur Jeż Faster Fully Compressed Pattern Matching by Recompression
15:25 – 15:45	Karl Bringmann and Konstantinos Panagiotou Efficient Sampling Methods for Discrete Distributions
Session IIIb. Track A3. Room MS.01
14:10 – 14:30	László Babai, Paolo Codenotti and Youming Qiao Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups
14:35 – 14:55	Lukas Polacek and Ola Svensson Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
15:00 – 15:20	Andrew Hughes, A Pavan, Nathan Russell and Alan Selman A Thirty Year Old Conjecture about Promise Problems
15:25 – 15:45	Hiro Ito, Shin-Ichi Tanigawa and Yuichi Yoshida Constant-Time Algorithms for Sparsity Matroids
Session IIIc. Track B2. Room MS.05
14:10 – 14:30	Maribel Fernandez and Albert Rubio Nominal Completion for Rewrite Systems with Binders
14:35 – 14:55	Mikołaj Bojańczyk and Thomas Place Toward Model Theory with Data Values
15:00 – 15:20	Mikołaj Bojańczyk and Sławomir Lasota A Machine-Independent Characterization of Timed Languages
15:25 – 15:45	Andrzej Murawski and Nikos Tzevelekos Algorithmic Games for Full Ground References
15:50 – 16:30	Coffee break
Session IV. BEST PAPER SESSION. Room MS.02
16:30 – 16:55	Best paper Track A	Leslie Ann Goldberg and Mark Jerrum The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)
17:00 – 17:25	Best paper Track B	Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter Regular Languages are Church-Rosser Congruential
17:30 – 17:55	Best paper Track C	Piotr Krysta and Berthold Vöcking Online Mechanism Design (Randomized Rounding on the Fly)
18:00 – 19:30	Welcome Reception Zeeman Building	Drinks and Canapés
Tuesday, July 10
Session V. Room MS.02
9:00 – 10:00	Invited Talk	Berthold Vöcking Randomised Mechanisms for Multi-Unit Auctions
10:00 – 10:30	Coffee break
Session VIa. Track A4. Room MS.02
10:30 – 10:50	Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk and Magnus Wahlstrom Clique cover and graph separation: New incompressibility results
10:55 – 11:15	Bingkai Lin and Yijia Chen The Parameterized Complexity of k-edge Induced Subgraphs
11:20 – 11:40	Rajesh Chitnis, Marek Cygan, Mohammadtaghi Hajiaghayi and Dániel Marx Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
11:45 – 12:05	Michael Fellows, Ariel Kulik, Frances Rosamond and Hadas Shachnai Parameterized Approximation via Fidelity Preserving Transformations
12:10 – 12:30	Rahul Santhanam and Srikanth Srinivasan On the Limits of Sparsification
Session VIb. Track A5. Room MS.01
10:30 – 10:50	Joshua Baron, Rafail Ostrovsky and Ivan Visconti Nearly Simultaneously Resettable Black-Box Zero Knowledge
10:55 – 11:15	Michael Rabin, Yishay Mansour, Muthu Muthuikrishnan and Moti Yung Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
11:20 – 11:40	Justin Thaler, Jonathan Ullman and Salil Vadhan Faster Algorithms for Privately Releasing Marginals
11:45 – 12:05	Anastasios Zouzias A Matrix Hyperbolic Cosine Algorithm and Applications
12:10 – 12:30	Amit Deshpande, Ravindran Kannan and Nikhil Srivastava Zero-One Rounding of Singular Vectors
Session VIc. Track B3. Room MS.05
10:30 – 10:50	Yaron Velner The Complexity of Mean-Payoff Automaton Expression
10:55 – 11:15	Gilles Dowek and Pablo Arrighi Causal Graph Dynamics
11:20 – 11:40	Patricia Bouyer, Nicolas Markey and Ocan Sankur Robust Reachability in Timed Automata: A Game-based Approach
11:45 – 12:05	Hongfei Fu Computing Game Metrics on Markov Decision Processes
12:10 – 12:30	Tomas Brazdil, Antonin Kucera, Petr Novotný and Dominik Wojtczak Minimizing Expected Termination Time in One-Counter Markov Decision Processes
12:45 – 14:00	Lunch
Session VIIa. Track A6. Room MS.02
14:10 – 14:30	Michael Kapralov and Rina Panigrahy NNS Lower Bounds via Metric Expansion for l∞ and EMD
14:35 – 14:55	T-H. Hubert Chan, Mingfei Li and Li Ning Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
15:00 – 15:20	Danny Z. Chen and Haitao Wang Computing the Visibility Polygon of an Island in a Polygonal Domain
Session VIIb. Track A7. Room MS.01
14:10 – 14:30	Jens M. Schmidt Certifying 3-Connectivitiy in Linear Time
14:35 – 14:55	Pushkar Tripathi, Prasad Tetali and Kevin Costello Stochastic Matching with Commitment
15:00 – 15:20	Loukas Georgiadis and Robert Tarjan Dominators, Directed Bipolar Orders, and Independent Spanning Trees
Session VIIc. Track C2. Room MS.05
14:10 – 14:30	Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald and He Sun Counting Arbitrary Subgraphs in Data Streams
14:35 – 14:55	Marcel Ochel, Klaus Radke and Berthold Vöcking Online Packing with Gradually Improving Capacity Estimations with Applications to Network Lifetime Maximization
15:00 – 15:20	Michael Goodrich and Michael Mitzenmacher Anonymous Card Shuffling and its Applications to Parallel Mixnets
15:25 – 16:00	Coffee break
Session VIII. Turing Talk and Presburger Award 2012. Room MS.02
16:00 – 17:00	Alan Turing Talk	David Harel Standing on the Shoulders of a Giant: One Person’s Experience of Turing’s Impact
17:00 – 17:05	Presentation of Presburger Award winners
17:05 – 17:30	Presburger Award 2012 co-winner:	Venkatesan Guruswami
17:30 – 17:55	Presburger Award 2012 co-winner:	Mihai Pătraşcu (talk by Mikkel Thorup)
Session IX. EATCS General Assembly. Room MS.02
18:00 – 19:30	EATCS General Assembly
Wednesday, July 11
Session X. Room MS.02
9:00 – 10:00	Invited Talk	Gilles Dowek A Theory Independent Curry-De Bruijn-Howard Correspondence
10:00 – 10:30	Coffee break
Session XIa. Track A8. Room MS.02
10:30 – 10:50	Elad Verbin and Qin Zhang Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
10:55 – 11:15	Maria Florina Balcan and Yingyu Liang Clustering under Perturbation Resilience
11:20 – 11:40	Justin Hsu, Sanjeev Khanna and Aaron Roth Distributed Private Heavy Hitters
11:45 – 12:05	Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan Quadratic Programming with a Ratio Objective
12:10 – 12:30	Kousha Etessami, Alistair Stewart and Mihalis Yannakakis Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
Session XIb. Track B4. Room MS.01
10:30 – 10:50	C.-H. Luke Ong and Takeshi Tsukada Two-Level Game Semantics, Intersection Types and Recursion Schemes
10:55 – 11:15	Sylvain Salvati, Giulio Manzonetto, Mai Gehrke and Henk Barendregt Loader and Urzyczyn are Logically Related
11:20 – 11:40	Chris Broadbent, Arnaud Carayol, Matthew Hague and Olivier Serre A Saturation Method for Collapsible Pushdown Systems
11:45 – 12:05	Christopher Broadbent Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata
12:10 – 12:30	Szymon Toruńczyk Languages of Profinite Words and the Limitedness Problem
Session XIc. Track C3. Room MS.05
10:30 – 10:50	Reuven Bar-Yehuda, Erez Kantor, Shay Kutten and Dror Rawitz Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs
10:55 – 11:15	Nishanth Chandran, Juan Garay and Rafail Ostrovsky Edge Fault Tolerance on Sparse Networks
11:20 – 11:40	Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth
11:45 – 12:05	Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach and Maurizio Patrignani Computational Complexity of Traffic Hijacking under BGP and S-BGP
12:10 – 12:30	Navendu Jain, Ishai Menache, Joseph Naor and F. Bruce Shepherd Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks
12:35 – 13:00	Collect your packed lunch (Refreshment area)
13:00 – 13:10	Conference Photograph
13:15 – 18:00	Excursion to Bletchley Park
18:00 – 20:00	Conference BBQ (Zeeman Building)
Thursday, July 12
Session XII. Room MS.02
9:00 – 10:00	Invited Talk	Daniel A. Spielman Algorithms, Graph Theory, and the Solution of Laplacian Linear Equation
10:00 – 10:30	Coffee break
Session XIIIa. Track A9. Room MS.02
10:30 – 10:50	Stacey Jeffery, Robin Kothari and Frédéric Magniez Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
10:55 – 11:15	Shelby Kimmel Quantum Adversary (Upper) Bound
11:20 – 11:40	Sevag Gharibian and Julia Kempe Hardness of Approximation for Quantum Problems
11:45 – 12:05	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
12:10 – 12:30	S. Laplante, V. Lerays and J. Roland Classical and Quantum Partition Bound and Detector Inefficiency
Session XIIIb. Track A10. Room MS.01
10:30 – 10:50	Sungjin Im, Viswanath Nagarajan and Ruben Van Der Zwaan Minimum Latency Submodular Cover
10:55 – 11:15	Robert Krauthgamer and Tamar Zondiner Preserving Terminal Distances using Minors
11:20 – 11:40	Marco Molinaro and R Ravi Geometry of Online Packing Linear Programs
11:45 – 12:05	Anupam Gupta and Viswanath Nagarajan Approximating Sparse Covering Integer Programs Online
12:10 – 12:30	Bundit Laekhanukit, Shayan Oveis Gharan and Mohit Singh An Improved Approximation Algorithm for The Minimum Size k-Arc Connected Subgraph Problem
Session XIIIc. Track B5. Room MS.05
10:30 – 10:50	Luca Aceto, Arnaud Carayol, Zoltan Esik and Anna Ingolfsdottir Algebraic Synchronization Trees and Processes
10:55 – 11:15	Tadeusz Litak, Dirk Pattinson, Katsuhiko Sano and Lutz Schröder Coalgebraic Predicate Logic
11:20 – 11:40	Marcelo Fiore Discrete Generalised Polynomial Functors
11:45 – 12:05	Uday Reddy and Brian Dunphy An Automata-Theoretic Model of Idealized Algol
12:10 – 12:30	Grigore Rosu and Andrei Stefanescu Towards a Unified Theory of Operational and Axiomatic Semantics
12:45 – 14:00	Buffet Lunch (Refreshment Area)
Session XIVa. Track A11. Room MS.02
14:10 – 14:30	Arash Farzan, Ian Munro and Rajeev Raman Succinct Indices for Range Queries with applications to Orthogonal Range Maxima
14:35 – 14:55	Prosenjit Bose, Sebastien Collette, Rolf Fagerberg and Stefan Langerman De-amortizing Binary Search Trees
15:00 – 15:20	Yaoyun Shi and Xiaodi Wu Epsilon-net Method for Optimizations over Separable States
15:25 – 15:45	Anupam Gupta and Kevin Lewi The Online Metric Matching Problem for Doubling Metrics
Session XIVb. Track A12. Room MS.01
14:10 – 14:30	Bruno Bauwens Complexity of Complexity and Maximal Plain versus Prefix-free Kolmogorov Complexity
14:35 – 14:55	Uriel Feige and Shlomo Jozeph Universal Factor Graphs
15:00 – 15:20	Yishay Mansour, Aviad Rubinstein, Shai Vardi and Ning Xie Converting Online Algorithms To Local Computation Algorithms
15:25 – 15:45	Michael Dinitz, Guy Kortsarz and Ran Raz Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
Session XIVc. Track C4. Room MS.05
14:10 – 14:30	David Peleg, Liam Roditty and Elad Tal Distributed Algorithms for Network Diameter and Girth
14:35 – 14:55	Leonid Barenboim On the Locality of NP-Complete Problems
15:00 – 15:20	Andrew Berns, James Hegeman and Sriram Pemmaraju Super-Fast Distributed Algorithms for Metric Facility Location
15:25 – 15:45	Yoann Dieudonne and Andrzej Pelc Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports
15:50 – 16:30	Coffee break
Session XV. Awards Ceremony. Room MS.02
16:30 – 16:45	Award Ceremony: Gödel Prize 2012 and EATCS Award 2012
16:45 – 17:45	Gödel Prize 2012 winners:	Elias Koutsoupias, Noam Nisan, Christos H. Papadimitriou, Amir Ronen, Tim Roughgarden, Éva Tardos
17:45 – 18:15	EATCS Award 2012 winner:	Moshe Vardi
18:30 – 22:30	Conference Dinner at Stoneleigh Abbey
Friday, July 13
Session XVI. Room MS.02
9:00 – 10:00	Invited Talk	Kohei Honda Session Types and Distributed Computing
10:00 – 10:30	Coffee break
Session XVIIa. Track A13. Room MS.02
10:30 – 10:50	Niv Buchbinder, Seffi Naor, R. Ravi and Mohit Singh Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
10:55 – 11:15	Moses Charikar and Shi Li A Dependent LP-rounding Approach for the k-Median Problem
11:20 – 11:40	Barna Saha and Samir Khuller Set Cover Revisited: Hypergraph Cover with Hard Capacities
11:45 – 12:05	Jaroslaw Byrka and Bartosz Rybicki Improved LP-rounding Approximation Algorithm for k-level Uncapacitated Facility Location
12:10 – 12:30	Chandra Chekuri, Alina Ene and Ali Vakilian Node-weighted Network Design in Planar and Minor-closed Families of Graphs
Session XVIIb. Track A14. Room MS.01
10:30 – 10:50	Robert Crowston, Mark Jones and Matthias Mnich Max-Cut Parameterized Above the Edwards-Erdős Bound
10:55 – 11:15	Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Magnus Wahlström Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
11:20 – 11:40	Daniel Lokshtanov and M. S. Ramanujan Parameterized Tractability of Multiway Cut with Parity Constraints
11:45 – 12:05	Dániel Marx A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
12:10 – 12:30	Philip Klein and Dániel Marx Solving Planar k-Terminal Cut in O(nc √k) Time
Session XVIIc. Track B6. Room MS.05
10:30 – 10:50	Mikołaj Bojańczyk and Thomas Place Regular Languages of Infinite Trees that are Boolean Combinations of Open Sets
10:55 – 11:15	Denis Kuperberg and Michael Vanden Boom On the Expressive Power of Cost Logics over Infinite Words
11:20 – 11:40	Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii and Michael Zakharyaschev Exponential Lower Bounds and Separation for Query Rewriting
11:45 – 12:05	Michael Benedikt, Pierre Bourhis and Pierre Senellart Monadic Datalog Containment
12:10 – 12:30	Rajeev Alur and Loris D'Antoni Streaming Tree Transducers
12:45 – 14:00	Lunch
Session XVIIIa. Track A15. Room MS.02
14:10 – 14:30	Magnus M. Halldorsson, Xiaoming Sun, Mario Szegedy and Chengu Wang Streaming and Communication Complexity of Clique Approximation
14:35 – 14:55	Reut Levi, Dana Ron and Ronitt Rubinfeld Testing Similar Means
15:00 – 15:20	Deeparnab Chakrabarty and Zhiyi Huang Testing Coverage Functions
15:25 – 15:45	Anil Ada, Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen The NOF Multiparty Communication Complexity of Composed Functions
Session XVIIIb. Track A16. Room MS.01
14:10 – 14:30	Serge Gaspers and Stefan Szeider Backdoors to Acyclic SAT
14:35 – 14:55	Anindya De, Ilias Diakonikolas and Rocco Servedio The Inverse Shapley Value Problem
15:00 – 15:20	Matthew Patitz, Robert Schweller, Bin Fu and Robert Sheline Self-Assembly with Geometric Tiles
15:25 – 15:45	Dimitris Achlioptas and Ricardo Menchaca-Mendez Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method
Session XVIIIc. Track C5. Room MS.05
14:10 – 14:30	Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden and Aneesh Sharma Preventing Unraveling in Social Networks: The Anchored k-Core Problem
14:35 – 14:55	Luca Gugelmann, Konstantinos Panagiotou and Ueli Peter Hyperbolic Random Graphs: Degree Sequence and Clustering
15:00 – 15:20	Ran Gelles, Rafail Ostrovsky and Kina Winoto Multi-User Equality Testing and Its Applications
15:25 – 15:45	Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam and Vassilis Zikas Byzantine Agreement with a Rational Adversary
15:50	Conference Close

---

All talks are taking place in Zeeman Building, Warwick Mathematics Institute, University of Warwick.

• Program Skeleton (pdf)
• Final Program (pdf)