Seminars
Seminars from previous years: 2022/23 2021/22 2020/21 2019/20 2018/19 2017/18 2016/17 2015/16 2014/15 2013/14 2012/13 2011/12 2010/11
ACiD Seminars 2023/24: Please email [email protected] for information on joining.
| Tues 3rd October 2023 13:00 MCS 2068 and online | Max Gadouleau (Durham) Words fixing the kernel network and maximum independent sets in graphs The simple greedy algorithm to find a maximal independent set of a graph can be viewed as a sequential update of a Boolean network, where the update function at each vertex is the conjunction of all the negated variables in its neighbourhood. In general, the convergence of the so-called kernel network is complex. A word (sequence of vertices) fixes the kernel network if applying the updates sequentially according to that word always leads to a fixed point whatever the initial configuration. We prove that determining whether a word fixes the kernel network is coNP-complete. We also consider the so-called permis, which are permutation words that fix the kernel network. We exhibit large classes of graphs that have a permis, but we also construct many graphs without a permis. This is joint work with David C. Kutner. |
| Tues 10th October 2023 13:00 MCS 2068 | ACiD Meeting! |
| Tues 17th October 2023 13:00 MCS 2068 and online | Rachael Colley (University of Glasgow) Measuring and Controlling Divisiveness in Rank Aggregation In rank aggregation, members of a population each rank a number of issues to decide which are collectively preferred. In this talk we will focus instead on identifying divisive issues that express disagreements among the preferences of individuals. We analyse the properties of our divisiveness measures and their relation to existing notions of polarisation. We also study their robustness under incomplete preferences and algorithms for control and manipulation of divisiveness. Our results advance our understanding of how to quantify disagreements in collective decision-making. Joint work with Umberto Grandi, César Hidalgo, Mariana Macedo, and Carlos Navarrete |
| Tues 24th October 2023 13:00 MCS 2068 | Naveen Garg (IIT Delhi) Capacitated Facility Location with Outliers In this talk I will present a simple local search algorithm for capacitated facility location when facility costs are uniform. Our algorithm is a 3.732-approximation and improves the 4-approximation of Kao. In the second part of the talk, I will consider the setting when we are permitted not to serve L clients (outliers). We extend the local search algorithm to obtain the first constant factor approximation for this problem. Our local search algorithm requires only 2 operations and is a 6.372-approximation. |
| Tues 31st October 2023 13:00 MCS 2068 and online | Mengxiao Zhang (Durham) Multi-unit Auction over a Social Network Diffusion auction is an emerging business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. We focus on designing mechanisms for multi-unit diffusion auctions. Despite numerous attempts at this problem, existing mechanisms either fail to be incentive compatible (IC) or achieve only an unsatisfactory level of social welfare (SW). Here, we propose a novel graph exploration technique to realise multi-item diffusion auction. This technique ensures that potential competition among buyers stay “localised” so as to facilitate truthful bidding. Using this technique, we design multi-unit diffusion auction mechanisms MUDAN and MUDAN-$m$. Both mechanisms satisfy, among other properties, IC and $1/m$-weak efficiency. We also show that they achieve optimal social welfare for the class of rewardless diffusion auctions. While MUDAN addresses the bottleneck case when each buyer demands only a single item, MUDAN-$m$ handles the more general, multi-demand setting. We further demonstrate that these mechanisms achieve near-optimal social welfare through experiments. |
| Tues 7th November 2023 13:00 MCS 2068 | |
| Tues 14th November 2023 13:00 MCS 2068 | Joachim Spoerhase (Sheffield) Parameterized Approximation Schemes for Clustering with General Norm Objectives This paper considers the well-studied algorithmic regime of designing a (1+epsilon)-approximation algorithm for a k-clustering problem that runs in time f(k,epsilon)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable previous results of this kind include EPASes in the high-dimensional Euclidean setting for k-center as well as k-median, and k-means. However, existing EPASes handle only basic objectives (such as k-center, k-median, and k-means) and are tailored to the specific objective and metric space. Our main contribution is a clean, simple, and unified algorithm that yields an EPAS for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, l-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics), and which is (almost) entirely oblivious to the underlying objective and metric space. Key to our approach is a new concept that we call bounded epsilon-scatter dimension — an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension. This is joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, and Roohani Sharma |
| Tues 21st November 2023 13:00 MCS 2068 | Silvia Butti (Oxford) Promise Valued CSPs: an algebraic framework for approximation problems The Promise Valued Constraint Satisfaction Problem (PVCSP) extends the CSP framework in two independent directions. In the promise setting, each constraint comes in a strong version and a weak version, and the task is to distinguish whether the input is satisfiable in the strong sense, or it is not satisfiable even in the weak sense. In the valued setting, each constraint has a cost, and the goal is to decide whether there exists an assignment whose total cost is smaller than a given threshold. PVCSPs combine and generalize both Promise and Valued CSPs and are general enough to include all constant-factor approximation problems for Max-CSP, such as approximate satisfiability of Boolean CNF-formulas. In this talk I will discuss a recently developed algebraic framework for obtaining complexity reductions between PVCSPs, heavily inspired by the highly successful algebraic approach to Promise CSPs. I will then show how some well-known inapproximability results can be explained in a new light using this framework. Joint work with Libor Barto, Alexandr Kazda, Caterina Viola, and Standa Živný. |
| Tues 28th November 2023 13:00 MCS 2068 | Robert Lieck (Durham) What do Music, Hyper-Graph Search, and Markov Chain Monte Carlo have in common? Music presents a range of interesting challenges to conventional inference methods. Some aspects can be modelled as a sequence of discrete events (similar to language/text) using probabilistic context-free grammars (PCFGs). Others require generalising 1) from discrete to continuous variables and/or 2) from sequential to non-sequential structures. While PCFGs have O(n^3 k) complexity (n: sequence length, k: alphabet size), exact solutions quickly become intractable in continuous and non-sequential settings requiring heuristics and approximate inference methods. In this talk, I will briefly highlight why music is such a multifaceted and fascinating problem to work on. I will then present some past [1], present and future work and challenges for inference with discrete-continuous, hierarchical, probabilistic models. [1] Lieck R, Rohrmeier M (2021) Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks. In: Advances in Neural Information Processing Systems 34. |
| Tues 5th December 2023 13:00 MCS 2068 | Lorenzo Ciardo (Oxford) TBA |
| Tues 9th January 2024 13:00 MCS 2068 | |
| Tues 16th January 2024 13:00 MCS 2068 | Noleen Köhler (Leeds) TBA |
| Tues 23rd January 2024 13:00 MCS 2068 | |
| Tues 30th January 2024 13:00 MCS 2068 | |
| Tues 6th February 2024 13:00 MCS 2068 | |
| Tues 13th February 2024 13:00 MCS 2068 | |
| Tues 20th February 2024 13:00 MCS 2068 | |
| Tues 27th February 2024 13:00 MCS 2068 | |
| Tues 5th March 2024 13:00 MCS 2068 | |
| Tues 12th March 2024 13:00 MCS 2068 | Natasha Shakhlevich (Leeds) TBA |