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
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
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
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
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
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
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
Incentive Ratios of Fisher Markets
10:55 – 11:15
Ilias Diakonikolas, Christos Papadimitriou, George Pierrakos and Yaron Singer
Efficiency-Revenue Trade-offs in Auctions
Efficiency-Revenue Trade-offs in Auctions
11:20 – 11:40
Khaled Elbassioni
A QPTAS for ε-Envy-Free Profit-Maximizing Pricing on Line Graphs
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
Contention Issues in Congestion Games
12:10 – 12:30
Fedor Fomin, Petr Golovach, Jesper Nederlof and Michał Pilipczuk
Minimizing Rosenthal Potential in Multicast Games
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
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
Pebble Games with Algebraic Rules
11:20 – 11:40
John Fearnley and Sven Schewe
Time and Parallelizability Results for Parity Games with Bounded Treewidth
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
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
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
CRAM: Compressed Random Access Memory
14:35 – 14:55
Yuval Emek, Magnus M. Halldorsson and Adi Rosen
Space-Constrained Interval Selection
Space-Constrained Interval Selection
15:00 – 15:20
Artur Jeż
Faster Fully Compressed Pattern Matching by Recompression
Faster Fully Compressed Pattern Matching by Recompression
15:25 – 15:45
Karl Bringmann and Konstantinos Panagiotou
Efficient Sampling Methods for Discrete Distributions
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
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
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
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
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
Nominal Completion for Rewrite Systems with Binders
14:35 – 14:55
Mikołaj Bojańczyk and Thomas Place
Toward Model Theory with Data Values
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
A Machine-Independent Characterization of Timed Languages
15:25 – 15:45
Andrzej Murawski and Nikos Tzevelekos
Algorithmic Games for Full Ground References
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)
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
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)
Online Mechanism Design (Randomized Rounding on the Fly)
18:00 – 19:30
Welcome Reception
Zeeman Building Drinks and Canapés
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
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
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
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
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
Parameterized Approximation via Fidelity Preserving Transformations
12:10 – 12:30
Rahul Santhanam and Srikanth Srinivasan
On the Limits of Sparsification
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
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
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
Faster Algorithms for Privately Releasing Marginals
11:45 – 12:05
Anastasios Zouzias
A Matrix Hyperbolic Cosine Algorithm and Applications
A Matrix Hyperbolic Cosine Algorithm and Applications
12:10 – 12:30
Amit Deshpande, Ravindran Kannan and Nikhil Srivastava
Zero-One Rounding of Singular Vectors
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
The Complexity of Mean-Payoff Automaton Expression
10:55 – 11:15
Gilles Dowek and Pablo Arrighi
Causal Graph Dynamics
Causal Graph Dynamics
11:20 – 11:40
Patricia Bouyer, Nicolas Markey and Ocan Sankur
Robust Reachability in Timed Automata: A Game-based Approach
Robust Reachability in Timed Automata: A Game-based Approach
11:45 – 12:05
Hongfei Fu
Computing Game Metrics on Markov Decision Processes
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
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
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
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
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
Certifying 3-Connectivitiy in Linear Time
14:35 – 14:55
Pushkar Tripathi, Prasad Tetali and Kevin Costello
Stochastic Matching with Commitment
Stochastic Matching with Commitment
15:00 – 15:20
Loukas Georgiadis and Robert Tarjan
Dominators, Directed Bipolar Orders, and Independent Spanning Trees
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
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
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
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
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
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
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
Clustering under Perturbation Resilience
11:20 – 11:40
Justin Hsu, Sanjeev Khanna and Aaron Roth
Distributed Private Heavy Hitters
Distributed Private Heavy Hitters
11:45 – 12:05
Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan
Quadratic Programming with a Ratio Objective
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
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
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
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
A Saturation Method for Collapsible Pushdown Systems
11:45 – 12:05
Christopher Broadbent
Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata
Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata
12:10 – 12:30
Szymon Toruńczyk
Languages of Profinite Words and the Limitedness Problem
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
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
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
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
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
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
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
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
10:55 – 11:15
Shelby Kimmel
Quantum Adversary (Upper) Bound
Quantum Adversary (Upper) Bound
11:20 – 11:40
Sevag Gharibian and Julia Kempe
Hardness of Approximation for Quantum Problems
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
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
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
Minimum Latency Submodular Cover
10:55 – 11:15
Robert Krauthgamer and Tamar Zondiner
Preserving Terminal Distances using Minors
Preserving Terminal Distances using Minors
11:20 – 11:40
Marco Molinaro and R Ravi
Geometry of Online Packing Linear Programs
Geometry of Online Packing Linear Programs
11:45 – 12:05
Anupam Gupta and Viswanath Nagarajan
Approximating Sparse Covering Integer Programs Online
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
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
Algebraic Synchronization Trees and Processes
10:55 – 11:15
Tadeusz Litak, Dirk Pattinson, Katsuhiko Sano and Lutz Schröder
Coalgebraic Predicate Logic
Coalgebraic Predicate Logic
11:20 – 11:40
Marcelo Fiore
Discrete Generalised Polynomial Functors
Discrete Generalised Polynomial Functors
11:45 – 12:05
Uday Reddy and Brian Dunphy
An Automata-Theoretic Model of Idealized Algol
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
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
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
De-amortizing Binary Search Trees
15:00 – 15:20
Yaoyun Shi and Xiaodi Wu
Epsilon-net Method for Optimizations over Separable States
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
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
Complexity of Complexity and Maximal Plain versus Prefix-free Kolmogorov Complexity
14:35 – 14:55
Uriel Feige and Shlomo Jozeph
Universal Factor Graphs
Universal Factor Graphs
15:00 – 15:20
Yishay Mansour, Aviad Rubinstein, Shai Vardi and Ning Xie
Converting Online Algorithms To Local Computation Algorithms
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
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
Distributed Algorithms for Network Diameter and Girth
14:35 – 14:55
Leonid Barenboim
On the Locality of NP-Complete Problems
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Exponential Lower Bounds and Separation for Query Rewriting
11:45 – 12:05
Michael Benedikt, Pierre Bourhis and Pierre Senellart
Monadic Datalog Containment
Monadic Datalog Containment
12:10 – 12:30
Rajeev Alur and Loris D'Antoni
Streaming Tree Transducers
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
Streaming and Communication Complexity of Clique Approximation
14:35 – 14:55
Reut Levi, Dana Ron and Ronitt Rubinfeld
Testing Similar Means
Testing Similar Means
15:00 – 15:20
Deeparnab Chakrabarty and Zhiyi Huang
Testing Coverage Functions
Testing Coverage Functions
15:25 – 15:45
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi and Phuong Nguyen
The NOF Multiparty Communication Complexity of Composed Functions
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
Backdoors to Acyclic SAT
14:35 – 14:55
Anindya De, Ilias Diakonikolas and Rocco Servedio
The Inverse Shapley Value Problem
The Inverse Shapley Value Problem
15:00 – 15:20
Matthew Patitz, Robert Schweller, Bin Fu and Robert Sheline
Self-Assembly with Geometric Tiles
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
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
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
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
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
Byzantine Agreement with a Rational Adversary
15:50
Conference Close
All talks are taking place in Zeeman Building, Warwick Mathematics Institute, University of Warwick.