Skip to main content

Conference Program

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.