Skip to main content

Seminars

Seminars from previous years: 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 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)
Tues 21st February 2022
13:00 MCS 2068 and online only
Xin Ye (Durham)
Tues 28th February 2023
13:00 MCS 2068 and online
Marta Piecyk (Warsaw University of Technology)
Tues 7th March 2023
13:00 MCS 2068 and online
Konrad Dabrowski (Newcastle)
Tues 14th March 2023
13:00 MCS 2068 and online
Tamio-Vesa Nakajima (Oxford)