Seminars from 2022/23

ACiD Seminars 2022/23: Please email [email protected] for information on joining.

Tues 4th October 2022 13:00 MCS 2068	ACiD Meeting!
Tues 11th October 2022 13:00 MCS 2068 and online	Isobel Friedlander (Durham) The MacWilliams Identity for the Skew-q-Product The weight distribution of an error correcting code is a crucial statistic in determining it’s effectiveness. One key tool for relating the weight of a code to that of it’s dual is the MacWilliams Identity, first developed for the Hamming metric. This talk develops a q-analog MacWilliams Identity in the form of a functional transformation for codes based on skew-symmetric matrices under their associated skew-rank metric. The method introduces a skew-q algebra and uses generalised Krawtchouk polynomials which is then extended to establish moments of the skew-rank distribution for these codes.
Tues 18th October 2022 13:00 MCS 2068 and online	Nina Klobas (Durham) Temporal Graphs Temporal graphs are graphs with a fixed vertex set and a set of edges that changes over time. This paradigm reflects the structure and operation of a great variety of modern networks, such as social networks, wired or wireless networks whose links change dynamically, transportation networks, etc. Mainly motivated by the fact that, due to causality, information can be transferred in a temporal graph along sequences of edges whose time-labels are increasing, the most traditional research on temporal graphs has focused on temporal paths and other “path-related” notions, such as e.g. temporal analogues of distance, reachability, and exploration. To complement this direction, several attempts have been recently made to define meaningful “non-path” temporal graph problems, which appropriately model specific applications, such as e.g. temporal analogs of matching, colouring, and vertex covert. In this talk we will introduce two different problems on temporal graphs (one path-related and one non-path related), and study their complexity.
Tues 25th October 2022 13:00 MCS 2068	Konstantinos Dogeas (Durham) Scheduling with predictions Using machine-learned predictions to create algorithms with better approximation guarantees is a very fresh and active field. In this talk, we’ll go through classic scheduling problems and try to improve their bounds using the learning augmented setting. More specifically, we’ll see classical settings under the objective of minimizing the sum of completion times and focus on the problem of scheduling jobs with arbitrary release dates on a single machine. In the new learning augmented setting, an algorithm which uses predictions to take decisions is both consistent — i.e. when the predictions are accurate, the performances of our algorithms are close to those of an optimal offline algorithm–, and robust — i.e. when the predictions are wrong, the performance of our algorithms are close to those of an online algorithm without predictions.
Tues 1st November 2022 13:00 online only	Jelle Oostveen (Utrecht University) Parameterized Complexity of Streaming Diameter and Connectivity Problems In this talk, we consider the parameterized complexity of Diameter and Connectivity in the streaming paradigm. The streaming paradigm is a model where our graph is not in memory, but we inspect it through the so-called “stream”. A focus on memory-efficiency is crucial in this setting. On the positive end, knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is O(log n) for any fixed k. On the negative end, many other parameters lead to lower bounds in the AL model, where Omega(n/p) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H.   This talk is based on joint work with Erik Jan van Leeuwen, available on arXiv (https://arxiv.org/abs/2207.04872). An extended abstract is to appear in the proceedings of IPEC 2022, and a version of this talk appeared at IPEC 2022.
Tues 8th November 2022 13:00 online only
Tues 15th November 2022 13:00 MCS 2068 and online	Puya Mirkarimi (Durham) MAX 2-SAT on continuous-time quantum computers The most popular approach to quantum computing is currently the quantum circuit model (or gate model), where a computation is carried out by applying a sequence of quantum gates to an initialised register of quantum bits (qubits) and performing measurements on the qubits. A separate family of methods, called continuous-time quantum computing, differs to the gate-based approach by evolving qubit states continuously in time, rather than in a way that is discretised into gates. My talk will begin with a brief introduction to quantum computing and its differences to classical computing, focusing on the continuous-time approach, which in practice is particularly suitable for solving hard combinatorial optimisation problems. I will then present an overview of recent work on comparing the relative hardness of instances of MAX 2-SAT for various continuous-time quantum algorithms and a particular classical algorithm (arXiv:2206.06876).
Tues 22nd November 2022 13:00 MCS 2068 and online	Chhaya Trehan (Bristol) A new and improved query strategy for finding a king in a tournament A tournament is an orientation of a complete graph. Given a tournament ‘T’, we say that a vertex ‘x’ in ‘T’ controls another vertex ‘y’, if there is a directed path of length at most two from ‘x’ to ‘y’ in ‘T’. A vertex is called a king if it controls every vertex of the tournament. It is well known that every tournament has a king. We follow Shen, Sheng, and Wu (SIAM J. Comput., 2003) in investigating the query complexity of finding a king, that is, the number of arcs in ‘T’ one has to know in order to surely identify atleast one vertex as a king. The aforementioned authors showed that one always has to query \Omega(n^{4/3}) arcs and provided a strategy that queries at most O(n^{3/2}). While this upper bound has not yet been improved for the original problem, Biswas et al. (Frontiers in Algorithmics, 2017) proved that with O(n^{4/3}) queries one can identify a semi-king, i.e., a vertex which controls at least half of the vertices. We present a novel query strategy that improves on the number of controlled vertices using O(n^{4/3}) queries. Specifically, we show that using O(n^{4/3} polylog n) queries, one can identify a vertex that controls at least (1/2 + 2/17) fraction of the vertices.
Tues 29th November 2022 13:00 MCS 2068 and online	David Kutner (Durham) Don’t skip bail! This talk introduces the Interval Debt Model (IDM), where nodes (banks) have debts (directed edges) to other nodes, labelled with the amount of the debt and the interval within which the debt must be paid. The problem of IDM Bailout Minimization is, given some IDM instance and amount b, whether it is feasible to allocate £b in total across the banks such that it is possible to create a payment schedule under which every debt is paid in full and on time. We show this problem to be (a) NP-Complete, even on paths and with b=0, if debts must be paid in full at a single timestep (b) NP-Complete, even on DAGs and with b=0, if we require all payments to be integer amounts, and (c) polynomial-time solvable as a linear program, if we allow payments to be fractional amounts.
Tues 6th December 2022 13:00 MCS 2068 and online	Martin Winter (Warwick) (Random) trees of intermediate volume growth We show that for every sufficiently well-behaved function g : N -> N that grows at least linearly and at most exponentially there exists a tree T of uniform volume growth g(r), or more precisely,   C1 · g(r/4) ≤ |B(v,r)| ≤ C2 · g(4r), for all r ≥ 0,   where B(v,r) denotes the ball of radius r centered at the vertex v. In particular, this yields examples for trees of uniform intermediate volume growth (i.e., super-polynomial but sub-exponential). This construction can be extended to yield unimodular random trees of uniform growth for the same wide range of growth behaviours, answering a question by Itai Benjamini. We investigate the structure of these random trees and find a threshold phenomenon, where these trees behave vastly different for growth below r^(log log r) versus growth above r^(a log log r) for any a > 1. This poses the question whether a similar phenomenon also occurs for general unimodular trees that are not necessarily constructed by our technique. This is joined work with George Kontogeorgiou (Warwick).
Tues 10th January 2023 13:00 MCS 2068 and online	Karl Southern (Durham) Side-channel resistant error correcting codes for post quantum cryptography As part of NIST’s post-quantum cryptography standardisation process, several schemes were submitted that made use of error correcting codes to reduce the decryption failure rates. Side-channel attacks are any form of attack which breaks an implementation of a scheme by making use of information gained from monitoring the encryption or decryption process. All of the schemes that made use of error correcting codes were broken by side-channel attacks that exploited the error correcting codes used. In this talk we introduce side-channel attacks and methods for securing against them, as well as presenting a side-channel resistant implementation of an error correcting code (Polar code).
Tues 17th January 2023 13:00 MCS 2068	ACiD Meeting!
Tues 24th January 2023 13:00 online only	Ville Salo (Turku) Reversible gates We define a simple model of computation based on reversible logical gates applied to a sequence of symbols from a finite alphabet. We prove a general existence theorem for universal gates and show a simple example of one. If time allows, we also outline some connections to automorphism groups of subshifts (equivalently, reversible cellular automata).
Tues 31st January 2023 13:00 MCS 2068 and online	Frank Kammer (TH Mittelhessen) Succinct Planar Encoding with Minor Operations Let G be an unlabeled planar and simple n-vertex graph. We present a succinct encoding of G that provides induced-minor operations, i.e., edge contraction and vertex deletions. Any sequence of such operations is processed in O(n) time. In addition, the encoding provides constant time per element neighborhood access and degree queries. Using optional hash tables the encoding additionally provides constant expected time adjacency queries as well as an edge-deletion operation (thus, all minor operations are supported) such that any number of such edge deletions are computed in O(n) expected time. Constructing the encoding requires O(n) bits and O(n) time. The encoding requires H(n)+o(n) bits of space with H(n) being the entropy of encoding a planar graph with n vertices. Our data structure is based on the recent result of Holm et al. [ESA 2017] who presented a linear time contraction data structure that allows to maintain parallel edges and works for labeled graphs, but uses O(n log n) bits of space. We combine the techniques used by Holm et al. with novel ideas and the succinct encoding of Blelloch and Farzan [CPM 2010] for arbitrary separable graphs. Our result partially answers the question raised by Blelloch and Farzan if their encoding can be modified to allow modifications of the graph.
Tues 7th February 2023 13:00 MCS 2068 and online	Felicia Lucke (University of Fribourg) Independent Set Transversals in Cocomparability Graphs For a given family of vertex sets C, a d-transversal of C is a set of vertices intersecting every set in C in at least d elements. Well known transversal problems are for example Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. In this talk we consider d-transversals of maximum independent sets, where we want the set S to be of minimum size and to intersect every maximum independent set in d elements. We will see how to represent independent sets in interval graphs as paths in a directed acyclic graph (DAG). We will extend this structure to independent sets in cocomparability graphs and use the resulting DAG to find a minimum d-transversal.
Tues 14th February 2023 13:00 online only	Kristina Asimi (Charles University) Promise CSP (standard and seen from the other side) This talk will be divided into two parts. In the first part we will talk about the standard Promise CSP (PCSP), where a pair of relational structures (A,B) (such that there is a homomorphism from A to B) is fixed and PCSP(A,B) is defined as the problem of deciding whether an input structure has a homomorphism to A or not even to B. In the second part of the talk we propose a similar problem, where we restrict the left-hand side instead of the right-hand side, motivated by the so-called left-hand side restricted CSP. Namely, we fix a class of pairs of relational structures C (such that for every pair there is a homomorphism from the first structure to the second one) and ask the following: for an input pair (A,B) from C and an input structure D, decide whether there is a homomorphism from B to D or not even from A to D.
Tues 21st February 2022 13:00 MCS 2068 and online	Xin Ye (Durham) Finding balanced solutions to international kidney exchange schemes For kidney patients, a treatment option is a kidney transplant. To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programs (IKEPs), countries merge their national patient-donor pools. The goal of IKEPs is not just to maximize the number of patients being treated, but to guarantee that participating countries receive the number of incoming kidneys as close as fair allocations. In this talk, I will model IKEPs in graph theory, with constraints on the exchanges, switching this problem into a matching problem, introduce the solution to allocations that maximizes the number of kidney patients being treated, and makes the deviation for every participating country from target allocations as small as possible, and present the simulation results to show the stability of this solution.
Tues 28th February 2023 13:00 online only	Marta Piecyk (Warsaw University of Technology) Coloring bounded-diameter graphs The 3-coloring problem is known to be NP-complete in general, and even, assuming the ETH, there is no subexponential-time algorithm. This holds even if we restrict the class of input graphs to the graphs with diameter at most 4. In 2013 Mertzios and Spirakis studied the 3-coloring problem on graphs with diameter 2 and 3. In case of diameter 3, they showed that the problem is NP-hard and in case of diameter 2, they provided an algorithm with running time 2^O(sqrt(n logn)). It is still not known if 3-coloring can be solved in polynomial time on diameter-2 graphs. During the talk I will present a sketch of an algorithm that solves 3-coloring on diameter-2 graphs in time 2^O(n^1/3 log^2 n). This is joint work with Michał Dębski and Paweł Rzążewski.
Tues 7th March 2023 13:00 MCS 2068 and online	Konrad Dabrowski (Newcastle) Learning Small Decision Trees for Data of Low Rank-Width A classification instance consists of a finite set E of examples (also called feature vectors). Each example e in E is a function e:feat(E) \to {0,1} which determines whether the feature f is true or false for e. The set E is given as a partition E^+ \uplus E^- into positive and negative examples. For instance, examples could represent medical patients and features diagnostic tests; a patient is positive or negative, corresponding to whether they have been diagnosed with a certain disease or not. The incidence graph G(E) is the bipartite graph with features and examples being the vertices, where an example is adjacent to all features that are true for it. A decision tree is a rooted binary tree whose internal nodes are features (with one child being negative and the other positive) and whose leaves are either 0 or 1, corresponding to negative and positive, respectively. A decision tree classifies a classification instance if we can correctly decide whether the example is positive or negative by going from the root to the leaves, always choosing the positive or negative child of a node if the example has that feature, or not, respectively. Finding a decision tree of smallest size is an NP-hard problem. We show that we can solve the problem in f(k)|E|^p time, where k is the rank-width of the incidence graph, f is a computable function independent of |E| and p is a constant. The talk will not assume any prior knowledge of graph widths or decision trees. I will explain the intuition behind how the algorithm works, and how to go about constructing such dynamic programming algorithms on graphs of bounded widths. Joint work with Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani and Stefan Szeider
Tues 28th March 2023 13:00 MCS 2051 and online	Jens Schlöter (Bremen) Set Selection under Explorable Stochastic Uncertainty via Covering Techniques Given subsets of uncertain values, we study the problem of identifying the subset of minimum total value (sum of the uncertain values) by querying as few values as possible. This set selection problem falls into the field of explorable uncertainty and is of intrinsic importance therein as it implies strong adversarial lower bounds for a wide range of interesting combinatorial problems such as knapsack and matchings. We consider a stochastic problem variant and give algorithms that, in expectation, improve upon these adversarial lower bounds. The key to our results is to prove a strong structural connection to a seemingly unrelated covering problem with uncertainty in the constraints via a linear programming formulation. We exploit this connection to derive an algorithmic framework that can be used to solve both problems under uncertainty, obtaining nearly tight bounds on the competitive ratio. This is the first non-trivial stochastic result in explorable uncertainty concerning the sum of unknown values without further structure known for the set. With our novel methods, we lay the foundations for solving more general problems in the area of explorable uncertainty.
NEW SLOT! Tues 25th April 2023 13:00 MCS 2068 and online	Tamio-Vesa Nakajima (Oxford) Boolean symmetric vs. functional PCSPs Constraint satisfaction problems are computational problems that ask us to find assignments of variables that satisfy certain constraints. One classical example of such a problem is solving systems of linear equations. These constraints have an interesting property: having fixed all but one variables in a constraint, the final variable is uniquely determined. If all of the constraints that can be imposed are of this form, then we call the corresponding template functional. This talk will look into the implications of functionality for promise constraint satisfaction problems. In such problems, one is promised that the input instance is solvable under stronger constraints, and is asked to find a solution under weaker constraints. We will show how if the strong constraints are symmetric and over a Boolean domain, and if the weak constraints are functional, then, depending on the language of allowed constraints, the problem is either NP-complete or solvable in polynomial time. Furthermore, all the solvable cases are essentially modular systems of linear equations in disguise. (Joint work with Stanislav Živný.)
NEW SLOT! Tues 16th May 2023 13:00 MCS 2068 and online	Navid Talebanfard (Sheffield) Linear Branching Programs and Directional Affine Extractors Bounded depth circuits have provided a fertile ground for research in the wilderness of complexity theory. We have tight circuit lower bounds, both worst-case and strong average-case, as well as size lower bounds in the proof complexity counterpart. But as soon as we allow modular gates, this clarity fades away. We do not have strong average-case lower bounds, and proving size lower bounds for bounded depth Frege system with modular gates is notoriously open. Motivated by these problems, we introduce notions of read-once branching programs with linear queries. We then define a property of functions which implies hardness against these programs. We also present a very explicit function with this property.   Joint work with Svyatoslav Gryaznov and Pavel Pudlák
Tues 23rd May 2023 13:00 MCS 2068 and online	ACiD Meeting!
Mon 12th June 2023 14:00 MCS 2050 and online	Banu Baklan Şen List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs Given a graph G = (V, E) and a list of available colors L(v) for each vertex v ∈ V, where L(v) ⊆ {1, 2, . . . , k}, LIST k-COLORING refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem LIST 3-COLORING is NP-complete even for bipartite graphs, and its complexity on comb-convex bipartite graphs has been an open problem. We give a polynomial-time algorithm to solve List 3-Coloring for caterpillar-convex bipartite graphs, a superclass of comb-convex bipartite graphs. We also give a polynomial-time recognition algorithm for the class of caterpillar-convex bipartite graphs. (Joint work with Öznur Yaşar Diner and Thomas Erlebach)