Programme
10:45 - 10:55 Coffee
10:55 - 11:00 Opening Remarks 11:00 - 11:40 Vincent Cohen-Addad (Recent Progress on Correlation Clustering: The Power of Sherali-Adams and New Practical insights) 11:40 - 12:20 Sagnik Mukhopadhyay (Simple Graph Algorithms that Work (Almost) Everywhere) 12:20 - 14:00 Lunch (Atrium of Zeeman Building) 14:00 - 14:40 Fabrizio Grandoni (Unsplittable Flow on a Path) 14:40 - 15:20 John Fearnley (Pure-Circuit: Tight Inapproximability within PPAD) 15:20 - 16:00 Isolde Adler (Logic and property testing on graphs of bounded degree) 16:00 - 16:30 Coffee break 16:30 - 17:10 Daniel Paulusma (A Complexity Framework For Forbidden Subgraphs) 17:10 - 17:50 Heng Guo (Towards derandomising Markov chain Monte Carlo) 18:00 - 19:00 Light Dinner (The Courtyard Restaurant in Scarman) |
Abstracts
Title: Logic and property testing on graphs of bounded degree
Abstract: Property testing (for a property P) asks for a given graph, whether it has property P, or is "structurally far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as "extremely efficient", making them relevant in the context of large data sets. In this talk I will present recent positive and negative results about testability of properties definable in first-order logic and monadic second-order logic on classes of bounded-degree graphs. This is joint work with Polly Fahey, Frederik Harwath, Noleen Köhler and Pan Peng. |
Title: Recent Progress on Correlation Clustering: The Power of Sherali-Adams and New Practical insights
Abstract: Correlation clustering is a classic model for clustering with several applications in data mining and unsupervised machine learning. In this problem, we are given a complete graph where each edge is labeled + or -; and the goal is to find a partition of the vertex set so as to minimize the number of + edges across the parts of the partition plus the number of - edges within the parts of the partition. We will first present a new result showing that a constant number of rounds of the Sherali-Adams hierarchy yields a strict improvement over the natural LP: we present the first better-than-two approximation for the problem, improving upon the previous approximation of 2.06 of Chawla, Makarychev, Schramm, Yaroslavtsev based on rounding the natural LP (which is known to have an integrality gap of 2). We will then review several recent ideas which have led to practical constant factor approximations to Correlation Clustering in various setups: distributed and parallel environments, differentially-private algorithms, dynamic algorithms, or sublinear time algorithms. This is a combination of joint works with Euiwoong Lee, Alantha Newman, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski, Chenglin Fan and Andreas Maggiori. |
Title: Pure-Circuit: Tight Inapproximability within PPAD
Abstract: I will talk about a new technique for showing strong inapproximability results within PPAD based on a new problem called Pure-Circuit. In particular, I will talk about a new hardness result for epsilon approximate well-supported equilibria (WSNE) in polymatrix games which applies for all epsilon < 1/3 and is tight for two-action games, a new hardness result for finding epsilon-WSNEs in graphical games for all epsilon < 1, which is tight for all games, and a new hardness result for finding epsilon approximate Nash equilibria in graphical games for all epsilon < 1/2, which is tight for two-action games. This is joint work with Argyrios Deligkas (Royal Holloway), Alexandros Hollender (Oxford & EPFL), and Themistoklis Melissourgos (Essex), and is presented in the following papers - Pure-Circuit: Strong Inapproximability in PPAD, FOCS 2022, to appear, available on arxiv. - Tight Inapproximability for Graphical Games, in submission, available on arxiv. |
Title: Unsplittable Flow on a Path
Abstract: In the unsplittable flow on a path problem (UFP) we are given a path graph with edge capacities. Furthermore we are given a collection of n tasks, where each task is characterized by a subpath, a demand, and a profit. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks using each edge e does not exceed the capacity of e. We might interpret the path as a time horizon subdivided into time slots (the edges). In this scenario, each task has to be executed in a specific time interval or not at all, and, if executed, it demands for a given amount of a time-varying resource (e.g., energy) and it provides a given revenue. I will overview the main results on the approximability of this NP-hard problem, culminating with a recent PTAS. I will also mention some related problems and open questions. |
Title: Towards derandomising Markov chain Monte Carlo
Abstract: We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling towards the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomisation. We provide two applications of this framework, namely efficient deterministic approximate counting algorithms for hypergraph independent sets and hypergraph colourings, under local lemma type conditions matching, up to lower order factors, their state-of-the-art randomised counterparts. Joint work with Weiming Feng, Chunyang Wang, Jiaheng Wang, and Yitong Yin |
Title: Simple Graph Algorithms that Work (Almost) Everywhere Abstract: I will talk about simple algorithms for cut and flow problems in the 2-party communication setting that can be adapted to many other distributed models of computation quickly. In the realm of data explosion, it is usually the case that a single computational processor is unable to store the vast amount of data needed to do any meaningful computation. We are indeed in the era of distributed computing, but it is not ideal to have different ad-hoc 'model-dependent' algorithms for solving the same problem. I will show recent progress in designing cross-paradigm algorithms that tackle this issue. I will show two examples: the minimum-cut problem (or min-cut) and the maximum bipartite matching problem (or BMM) where, in each case, a simple schematic algorithm can be implemented in a number of computational models to achieve the optimal complexity. This is a culmination of a number of papers that appeared in the last couple of years with coauthors Joakim Blikstad, Jan van den Brand, Yuval Efron, Troy Lee, Simon Apers, Pawel Gawrychowski, Michal Dory, Andrés López-Martínez and Danupon Nanongkai. |
Title: A Complexity Framework For Forbidden Subgraphs Abstract: For a finite set H of graphs, a graph is H-subgraph-free if it does not contain any of the graphs from H as a subgraph. We propose a meta-theorem to classify if graph problems are “efficiently solvable” or “computationally hard” on H-subgraph-free graphs. The conditions of the meta-theorem are that the problem should be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness is maintained under edge subdivision. All problems that satisfy these conditions are shown to be efficiently solvable if H contains a graph that is a disjoint union of a set of paths and subdivided claws, and are computationally hard otherwise. To illustrate the broad applicability of our framework, we study NP-complete problems that are either covering problems, network design problems or width parameter problems. We apply the framework to obtain a dichotomy between polynomial-time solvability and NP-completeness. We also study polynomial-time solvable problems, and apply the framework to obtain a dichotomy between linear-time solvability and having no subquadratic-time algorithm conditioned on appropriate hardness hypotheses. Based on joint work with Matthew Johnson, Barnaby Martin, Jelle Oostveen, Sukanya Pandey, Siani Smith and Erik Jan van Leeuwen. |