NESTiD Seminar 2022/23
NESTiD Seminar 2022/23
Below you can find the list of speakers and talks for the year 2022/23.
The seminar talks every two weeks were co-organized together with the research group of Networks and Distributed Computing at the University of Liverpool, as part of the Durham-Liverpool synergy. The contact person of this synergy in Liverpool is Leszek Gasieniec.
NESTiD Seminar Coordinator: George Mertzios
Link for the Seminar videos of 2022/23: click here
Previous years’ seminars are listed here
Term 1 of 2022/23:
(talks also streamed over zoom)
| Date and Time | Talk |
|---|---|
| Thursday 6 Oct 2022 16:15 – 17:15 (Inaugural talk of the NESTiD seminar series) (Please note the different room: D/L50 in the Psychology building) | Artur Czumaj (University of Warwick, UK) Parallel Connectivity We study the parallel complexity of graph connectivity, one of the most basic and fundamental optimization problems on graphs. We will focus on the nowadays classical model of Massive Parallel Computation (MPC), which follows the framework of MapReduce systems. The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only O(n^δ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. While it is not difficult to see that the problem can be solved in O(log n) MPC rounds, in a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O(log D + loglog n) rounds on an MPC with low local space determine all connected components of a graph. In this talk I will present the main ideas behind these algorithms and then show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O(logD + loglogn) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc. We complement our upper bounds by presenting an almost matching lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture. This is based on a joint work with Sam Coy that appeared at STOC’2022. |
| Thursday 13 Oct 2022 16:15 – 17:15 (Inaugural talk of the seminar series of the Durham-Liverpool synergy) | Christian Konrad (University of Bristol, UK) Dominating set in graph streams and beyond We resolve the space complexity of one-pass streaming algorithms for Minimum Dominating Set (MDS) in both insertion-only and insertion-deletion streams (up to poly-logarithmic factors) where an input graph is revealed by a sequence of edge updates. Recently, streaming algorithms for the related Set Cover problem, where entire sets arrive one-by-one, have received significant attention. Even though MDS can be viewed as a special case of Set Cover, MDS is harder to solve in the streaming setting since the input stream consists of individual edges rather than entire vertex-neighbourhoods, as in the case of Set Cover. 1) In insertion-only streams, we give a one-pass semi-streaming algorithm (meaning Õ(n) space) with approximation factor Õ(√n). We also prove that every one-pass streaming algorithm with space o(n) has an approximation factor of Ω(n/log n). Combined with a result by [Assadi et al., STOC’16] for Set Cover which, translated to MDS, shows that space Θ̃(n² / α) is necessary and sufficient for computing an α-approximation for every α = o(√n), this completely settles the space requirements for MDS in the insertion-only setting. 2) In insertion-deletion streams, we prove that space Ω(n² / (α log n)) is necessary for every approximation factor α ≤ Θ(n / log³ n). Combined with the Set Cover algorithm of [Assadi et al., STOC’16], which can be adapted to MDS even in the insertion-deletion setting to give an α-approximation in Õ(n² / α) space, this completely settles the space requirements for MDS in the insertion-deletion setting. We will also discuss recent developments regarding the edge-arrival version of the Set Cover problem, i.e., where sets are revealed as a sequence of tuples (S_i, u) in arbitrary order, indicating that element u is contained in set S_i. This is based on joint work with Sanjeev Khanna and Cezar-Mihail Alexandru. |
| Thursday 20 Oct 2022 16:15 – 17:15 | Ya-Chun Liang (University of Liverpool, UK) Improving the Bounds of the Online Dynamic Power Management Problem Machines consume energy and many of them have the following property: namely machines have two states, ON and OFF, and change between the two states quite often. Furthermore, it requires a relatively large amount of energy to change from OFF to ON. We investigate the power-down mechanism which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle cost and switching cost, is minimized. In contrast to most of the previous studies on the offline model, we focus on the online model in which a sequence of jobs with their release time, execution time and deadline, arrive in an online fashion. In this talk, we present a different switching on and off strategy and show an upper bound of 3, improving the currently best bound of 4, and further prove a better lower bound of 2.1, in a dual-machine model. |
| Thursday 27 Oct 2022 16:15 – 17:15 (Durham-Liverpool synergy) | Sebastian Wild (University of Liverpool, UK) Putting your graphs on a diet: Centralized and distributed representations for classes of graphs This talk will discuss different models for space-efficient representations of graphs and how they relate. The first model is that of succinct data structures, where all data is held centrally and the emphasis is on supporting certain queries (such as adjacency, degree, neighbors, but also (unweighted) shortest-path distance) efficiently while using close to the information-theoretic minimum of space. Such representations can be used as a drop-in replacement for an adjacency-list representation. I will present some recent results on permutation graphs along these lines and introduce the building blocks of space-efficient data structures used therein. The second model is that of graph labeling schemes, where the graph is stored in a distributed fashion: Each vertex is assigned a label so that the query under consideration (e.g. adjacency) can be answered from only seeing the labels of the involved vertices. Labeling schemes for the adjacency query are also known as implicit graph representations, which are the subject of the recently refuted, long-standing Implicit Graph Conjecture (IGC). I will summarize our recent work on randomized graph labeling schemes and its connection to the IGC. I will finally show an example where a centralized, succinct data structure uses strictly less space than any graph labeling scheme can achieve; this example thus exhibits an inherent space overhead for decentralized computation. This talk is based on joint work with Nathaniel Harms and Viktor Zamaraev [1] and joint work with Konstantinos Tsakalidis and Viktor Zamaraev [2]. [1] “Randomized Communication and Implicit Graph Representations”, STOC 2022, https://www.wild-inter.net/publications/harms-wild-zamaraev-2022 [2] “Succinct Permutation Graphs”, Algorithmica 2022, https://www.wild-inter.net/publications/tsakalidis-wild-zamaraev-2022 |
| Thursday 3 Nov 2022 16:15 – 17:15 | Wei Wang (Huazhong University of Science and Technology, China) MetaV: Mobile Communication/Computing Enhanced Intelligence in Connected and Autonomous Vehicles The global transportation sector is facing an increasing safety crisis with an estimated 1.2 million people killed on the world’s road every year. To improve transport efficiency and safety, connected and autonomous vehicles (CAVs) leverage distinct sensing modalities and dynamic networking to break through the perception limitation of a single vehicle. CAV is an integration of two of the most promising automotive technologies, connected vehicles and autonomous vehicles. In CAV local perception from autonomous vehicles is shared with other vehicles and infrastructure to build a comprehensive perception of driving environments and cooperative driving. This talk will present our recent efforts to address several essential challenges in achieving CAV. In particular, this talk will introduce a spatial-temporal adaptive computation offloading solution for video semantic segmentation in CAV to address the bandwidth limitation issue, a mmwave automotive radar metric localization solution to address the Doppler effect issue, and a wireless-assisted vision SLAM solution to extend it to dark and textureless environments. |
| Thursday 10 Nov 2022 16:15 – 17:15 (Durham-Liverpool synergy) | Michal Dory (University of Haifa, Israel) Distance Computation in Massive Graphs Computing distances in a graph is one of the most fundamental problems in graph algorithms. But how can we solve it when the input graph is too large and cannot be stored in one computer? In this talk, I will discuss a recent line of work that led to extremely fast distributed algorithms for approximating shortest paths, improving exponentially over the state-of-the-art. |
| Thursday 17 Nov 2022 16:15 – 17:15 | |
| Thursday 24 Nov 2022 16:15 – 17:15 (Durham-Liverpool synergy) | Evangelos Kranakis (Carleton University, Canada) The Bomb Squad Two cooperating, autonomous mobile robots with arbitrary nonzero max speeds are placed at arbitrary initial positions in the plane. A remotely detonated bomb is discovered at some source location and must be moved to a safe distance away from its initial location as quickly as possible. In the Bomb Squad problem, the robots cooperate by communicating face-to-face in order to pick up the bomb from the source and carry it away to the boundary of a disk centered at the source in the shortest possible time. The goal is to specify trajectories which define the robots’ paths from start to finish and their meeting points which enable face-to-face collaboration by exchanging information and passing the bomb from robot to robot. We design algorithms reflecting the robots’ knowledge about orientation and each other’s speed and location. In the offline case, we design an optimal algorithm. For the limited knowledge cases, we provide online algorithms which consider robots’ level of agreement on orientation as per OneAxis and NoAxis models, and knowledge of the boundary as per Visible, Discoverable, and Invisible. In all cases, we analyze the competitive ratios of the online problems. Joint Work with Jared Coleman, Danny Krizanc, Oscar Morales-Ponce. |
| Thursday 1 Dec 2022 16:15 – 17:15 | Thomas Erlebach (Durham University, UK) Explorable Uncertainty and Untrusted Predictions The research area of explorable uncertainty is concerned with problems where some of the input data is uncertain, but queries can be executed to reveal the true values of uncertain input elements. Uncertain values are typically given in the form of intervals. The goal is to minimise the number of queries that are needed until a provably correct solution can be output. In addition to the intervals, we may have access to predictions of the true values, possibly obtained via machine learning. Our aim is then to devise query strategies that benefit from accurate predictions but do not get misled too much by incorrect predictions. In this talk, we will discuss some recent progress in this combined setting, including query strategies for minimum spanning trees with edge uncertainty that benefit from good predictions while maintaining the best possible worst-case competitive ratio even if the predictions are arbitrarily wrong. The talk is mainly based on joint work with Murilo Santos de Lima, Nicole Megow and Jens Schlöter. |
| Thursday 8 Dec 2022 16:15 – 17:15 (Durham-Liverpool synergy) | Magnus Halldorsson (Reykjavik University, Iceland) Distributed graph coloring: The loglog-revolution The graph coloring problem is fundamental to distributed computing, as an elegant way of breaking symmetry and sharing resources. For the core problem of using $\Delta+1$ colors, where $\Delta$ is the maximum degree, a randomized algorithm of Chang, Li and Pettie [STOC’18] achieves the best complexity known of $O(\log^3 \log n)$ rounds of the LOCAL model, when combined with the recent deterministic algorithm of Ghaffari and Kuhn [FOCS’21]. We describe recent results that are simpler, faster, more general, use fewer colors, and/or are bandwidth efficient. In particular, we give a simplified framework that holds in the CONGEST model and is ultrafast when $\Delta$ is sufficiently large. We apply it to get fast algorithms for the more general degree+1-list coloring and the $\Delta$-coloring problems. This is joint work with Manuela Fischer, Fabian Kuhn, Yannic Maus, Alexandre Nolin, and Tigran Tonoyan, appearing in STOC’21, STOC’22, SIROCCO’22, and SODA’23. |
Term 2 of 2022/23:
(talks also streamed over zoom)
| Thursday 12 Jan 2023 16:00 – 17:00 | Peter Davies (Durham University, UK) Improved Distributed Algorithms for the Lovász Local Lemma The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have n `bad events’, each of which occurs with probability at most p and is independent of all but d other events, then under certain criteria on p and d, all of the bad events can be avoided with positive probability. While the original proof was existential, there has been much study on the algorithmic Lovász Local Lemma: that is, designing an algorithm which finds an assignment of the underlying random variables such that all the bad events are indeed avoided. Notably, the celebrated result of Moser and Tardos also implied an efficient distributed algorithm for the problem, running in O(log^2 n) rounds. For instances with low d, this was improved to O(d^2+log^{O(1)} log n) by Fischer and Ghaffari, a result that has proven highly important in distributed complexity theory. In this talk, I will present an improved algorithm for the Lovász Local Lemma, yielding a faster distributed round complexity and providing a trade-off agianst the strength of the criterion relating p and d. I will also mention some of its applications, including the first logO(1)logn-round distributed algorithm for the problem of Δ+o(Δ)-edge coloring a graph of maximum degree Δ. |
| Thursday 19 Jan 2023 16:00 – 17:00 (Durham-Liverpool synergy) | Laurent Feuilloley (CNRS, LIRIS, University of Lyon, France) An overview of local certification Local certification is a notion of the theory of distributed computing that originates from the study of self-stabilization. Basically, it consists in a labeling of the nodes of a network that allows the nodes to locally verify a global property. In this talk I will introduce the notion, describe its origins, basic properties, and give a quick overview on the current research on this topic. |
| Thursday 26 Jan 2023 16:00 – 17:00 (Durham-Liverpool synergy) | Hagit Attiya (Technion, Israel) Preserving Hyperproperties when Using Concurrent Objects Linearizability, a consistency condition for concurrent objects, is known to preserve trace properties. This suffices for modular usage of concurrent objects in applications, deriving their safety properties from the abstract object they implement. However, other desirable properties, like average complexity and information leakage, are not trace properties. These *hyperproperties* are not preserved by linearizable concurrent objects, especially when randomization is used. This talk will discuss formal ways to specify concurrent objects that preserve hyperproperties and their relation with verification methods like forward / backward simulation. We will show that certain concurrent objects cannot satisfy such specifications, and describe ways to mitigate these limitations. This is a joint work with Constantin Enea and Jennifer Welch. |
| Thursday 2 Feb 2023 16:00 – 17:00 (Durham-Liverpool synergy) | Leandros Tassiulas (Yale, USA) – THIS TALK WAS CANCELED AND WILL BE RESCHEDULED AT A LATER TIME – |
| Thursday 9 Feb 2023 16:00 – 17:00 | Posco Tso (Loughborough University, UK) Fine-grained Composition of Service Function Chains in the Programmable Data Plane Dynamic service function chains (SFC) are enabled by network function virtualization on general purpose servers. The emergence of programmable data plane (PDP) has offered a new way for the deployment of SFC. However, the implementation of network functions is constrained by resource limitations in PDP (e.g., compute and memory resource). Moreover, most of existing works do not consider the optimization of state information (e.g., registers), which is essential for stateful network functions. In this talk, I will introduce pSFC — a fine-grained SFC deployment scheme in the PDP for tackling this challenge. We first model network functions as control flow graphs (CFG) and the process of deployment as a one big switch (OBS) problem, and then propose an Integer Linear Programming (ILP) model for resource optimization for the OBS problem, which is NP-hard. To solve this problem efficiently, pSFC first composes multiple SFCs for eliminating redundant resources, decomposes the compound CFG based on the resource limitation per stage, and finally maps OBS into the substrate network. We have implemented pSFC in both bmv2 software switch and an Intel Tofino P4 hardware switch. Evaluation shows that pSFC reduces switch costs 45.7% and average latency by 22% without compromising throughput. |
| Thursday 16 Feb 2023 16:00 – 17:00 | Cormac J. Sreenan (MENU University College Cork, Ireland) Improving Quality of Experience for Video Users in Cellular Networks Video streaming has become the dominant traffic type on cellular networks. It continues to present challenges, due to the variability of network performance, increased demand, and greater quality expectations from users. In this seminar, I will focus on our work on the iViD project to improve video streaming over wireless networks. This will include using machine learning for throughout prediction and how to employ this effectively in video players. I will also describe our published 4G/5G/video datasets. The approach will be to explain the rationale for the research, the evolution of our solutions, choice of methodologies, and remaining challenges. I will also briefly introduce CONNECT, which is the Irish research centre for future networks and communications, within which much of my work is conducted. |
| Thursday 23 Feb 2023 16:00 – 17:00 | ! ! ! ! ! THIS SEMINAR WAS CANCELED DUE TO INDUSTRIAL ACTION AND WILL BE GIVEN IN 2023-24 ! ! ! ! ! Kieran Fernandes(Durham University Business School, UK) Smart Cities Cities play an important role in tackling climate change due to human population and the evergrowing pressure on energy usage. My presentation will discuss how cities can respond to the circularity challenge by proposing a social contract model to engage the quadruple stakeholders in developing inclusive, safe, resilient and sustainable cities – which contributes directly to SDGs 8 & 11. We identify the following eight factors that are essential to this social contract and are detailed in this report: Innovation & Technology, People & Human Resources, Wellness, Health, Education & Liveability, Financial Funding, Leadership & Governance, Business Professional ESR, Circular Economy and Energy Net Neutrality. and Atanu Chaudhuri (Durham University Business School, UK) Performance Impact and capabilities needed for Blockchain implementation in Supply Chains: Findings from case studies and econometric modelling This presentation is based on Atanu’s recently published qualitative case study research on the role of blockchain in reducing transaction costs, improving quality, risk management and social sustainability across the chain and the capabilities needed to deliver Blockchain implementation projects. Atanu will also talk about the impact of announcements of Blockchain implemenation on stock prices and operating performance based on data of 136 Blockchain implementation projects in the supply chain. |
| Thursday 2 Mar 2023 16:00 – 17:00 | Charles Dodd (York University, UK) Hellman-like attacks on passwords Hellman tables allow an adversary to pre-process a space of possible passwords. By picking random points and iterating the hash function to form hash chains of a set length, an adversary can cover the space. By only storing the chain endpoints, the space required to store the hash pre-images is greatly reduced. Of course, collisions in the hash chains become likely at this scale, and while some can be removed in the table generation the remaining collisions complicate the calculation of adversarial advantage. Further difficulties arise in attempting to adapt the technique to passwords stored under iterated hashes. This presentation is based on joint work with Dr Farshim, Dr Shahandashti and Karl Southern. I will present the idea of a Hellman table, looking at the adversarial upper and lower bounds. Then present the work we have on extending Hellman tables to passwords stored under iterated hashes. The highlights are a new variant of the Hellman table for iterated hashes, and an application of the pre-sampling technique for calculating upper bounds in the auxiliary input setting. |
| Thursday 9 Mar 2023 16:00 – 17:00 | Radu Prodan (Alpen-Adria University Klagenfurt, Austria) Extreme and Sustainable Graph Processing for Urgent Societal Challenges in Europe: The Graph-Massivizer project Graph-Massivizer is a Horizon Europe project that researches and develops a high-performance, scalable, and sustainable platform for information processing and reasoning based on the massive graph representation of extreme data. It delivers a toolkit of five open-source software tools and FAIR graph datasets covering the sustainable lifecycle of processing extreme data as massive graphs. The tools focus on holistic usability (from extreme data ingestion and massive graph creation), automated intelligence (through analytics and reasoning), performance modelling, and environmental sustainability tradeoffs, supported by credible data-driven evidence across the computing continuum. The automated operation based on the emerging serverless computing paradigm supports experienced and novice stakeholders from a broad group of large and small organisations to capitalise on extreme data through massive graph programming and processing. Graph Massivizer validates its innovation on four complementary use cases considering their extreme data properties and coverage of the three sustainability pillars (economy, society, and environment): sustainable green finance, global environment protection foresight, green AI for the sustainable automotive industry, and data centre digital twin for exascale computing. Graph Massivizer promises 70% more efficient analytics than AliGraph, and 30% improved energy awareness for ETL storage operations than Amazon Redshift. Furthermore, it aims to demonstrate a possible two-fold improvement in data centre energy efficiency and over 25% lower GHG emissions for basic graph operations. Graph-Massivizer gathers an interdisciplinary group of twelve partners from eight countries, covering four academic universities, two applied research centres, one HPC centre, two SMEs and two large enterprises. It leverages the world-leading roles of European researchers in graph processing and serverless computing and uses leadership-class European infrastructure in the computing continuum. |
| Thursday 16 Mar 2023 16:00 – 17:00 | ! ! ! ! ! THIS SEMINAR WAS CANCELED DUE TO INDUSTRIAL ACTION AND WILL BE GIVEN IN 2023-24 ! ! ! ! ! William Moses (University of Durham, UK) TBA |
Term 3 of 2022/23:
(talks also streamed over zoom)
| Thursday 27 Apr 2023 16:00 – 17:00 | Sagnik Mukhopadhyay (University of Sheffield, UK) ! ! ! ! ! THIS SEMINAR WAS CANCELED DUE TO INDUSTRIAL ACTION AND WILL BE GIVEN IN 2023-24 ! ! ! ! ! |
| Thursday 4 May 2023 16:00 – 17:00 | Jason Schoeters (LITIS lab and University of Le Havre, France) Journey-based components in temporal graphs Temporal graphs are graphs in which edges can appear and disappear over time. We partly answer the question “What does a connected component correspond to in temporal graphs?” Indeed, many forms of connectivity exist in temporal graphs, some of which are defined with journeys, i.e. composed of successive edges in time. We present some results concerning components defined with journeys. After a general introduction presenting among other things the hierarchy of temporal connectivity, we study $\mathcal{S}$ components, where there is a source vertex which can reach all the other vertices of the component through journeys. Structural and algorithmic results are given. We generalize by considering sliding time windows, closed components (journeys remain inside the component), and/or allowing the source to change between windows. Finally, we complete results concerning $\mathcal{TC}$(-like) components, where each vertex must reach each other vertex, for which we additionally study more finely the complexity concerning fixed graph lifetimes. This is a joined work with Stefan Balev, Yoann Pigné and Eric Sanlaville. |