Date and Time: October 6th 2022, Thursday, 13:00 CEST

Speaker: Vera Traub, University of Bonn

Host: Andreas Karrenbauer, Max Planck Institute for Informatics

Title: Better-Than-2 Approximations for Weighted Tree Augmentation and Forest Augmentation

Abstract: The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. In the first part of this talk we present the first algorithm that improves on the longstanding approximation ratio of 2 for WTAP.

In the second part of the talk we show how this algorithm can be used to obtain the first better-than-2 approximation algorithm for the Forest Augmentation Problem. In this problem we want to choose a minimum number of edges, among a given set of options, that we can add to a graph G to make it 2-edge connected. In contrast to the Tree Augmentation Problem, we do not require the given graph G to be connected.

This talk is based on joint works with Fabrizio Grandoni, Afrouz Jabal Ameli, and Rico Zenklusen.

Date and Time: Sept 20, 2022, Tuesday, 13:00 CEST

Speaker: Merav Parter, Weizmann Institute of Science

Host: Christoph Lenzen, CISPA Helmholtz Center for Information Security

Title: A Graph Theoretic Approach for Resilient Distributed Algorithms

Abstract: Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice.

In this talk, I will present a unified framework for obtaining fast, resilient and secure distributed algorithms for fundamental graph problems. Our approach is based on a graph-theoretic perspective in which common notions of resilient requirements are translated into suitably tailored combinatorial graph structures. We will discuss recent developments along the following two lines of research:

- Designing distributed algorithms that can handle various adversarial settings, such as, node crashes and Byzantine attacks. We will mainly provide general compilation schemes that are based on exploiting the high-connectivity of the graph. Our key focus will be on the efficiency of the resilient algorithms in terms of the number of communication rounds.

- Initiating and establishing the theoretical exploration of security in distributed graph algorithms. Such a notion has been addressed before mainly in the context of secure multi-party computation (MPC). The heart of our approach is to develop new graph theoretical infrastructures to provide graphical secure channels between nodes in a communication network of an arbitrary topology.

Finally, I will highlight future directions that call for strengthening the connections between the areas of fault tolerant network design, distributed graph algorithms and information theoretic security.

Date and Time: Sept 22, 2022, Tuesday, 16:00 CEST

Speaker: Ariel Procaccia, Harvard University

Host : Kurt Mehlhorn, Max Planck Institute for Informatics

Title: Democracy and the Pursuit of Randomness

Abstract: Sortition is a storied paradigm of democracy built on the idea of choosing representatives through lotteries instead of elections. In recent years this idea has found renewed popularity in the form of citizens' assemblies, which bring together randomly selected people from all walks of life to discuss key questions and deliver policy recommendations. A principled approach to sortition, however, must resolve the tension between two competing requirements: that the demographic composition of citizens' assemblies reflect the general population and that every person be given a fair chance (literally) to participate. I will describe our work on designing, analyzing and implementing randomized participant selection algorithms that balance these two requirements. I will also discuss practical challenges in sortition based on experience with the adoption and deployment of our open-source system, Panelot.