Date and Time: Feb 02, 2023, Thursday, 13:00 CET

Speaker: Jukka Suomela, Aalto University, Finland

Host: Christoph Lenzen, CISPA Helmholtz Center for Information Security

Title: TBA

Abstract: TBA

Date and Time: Feb 21, 2023, Thursday, 13:00 CET

Speaker : Ryan Williams, MIT, USA,

Host : Markus Blaeser, Saarland University

Title: TBA

Abstract: TBA

Date and Time: Dec 20, 2022, Tuesday, 16:00 CET

Speaker: Yury Makarychev, Toyota Technological Institute Chicago, United States

Host: Joachim Spoerhase, MPI-INF

Title: Approximation algorithms for the socially fair clustering problem

Abstract: We will discuss the socially fair clustering problem. In this problem, we are given a set of points in a metric space; each point is assigned to one of ℓ groups. The goal is to find a k-medians, k-means, or, more generally, ℓ_p-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of the sum ∑ d(u,C)^p, where u belongs to group j. We present an O(log ℓ / log log ℓ) approximation algorithm for this problem. We also study a more general (p, q)-fair clustering problem.

Date and Time: Dec 13, 2022, Tuesday, 13:00 CET

Speaker: Eva Rotenberg, DTU, Denmark

Host: Karl Bringmann, Saarland University

Title: Sparsity-adaptive dynamic graph algorithms

Abstract: Based on joint work with: Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog, Krzysztof D. Nowicki, Chris Schwiegelshohn, and Carsten Thomassen

The arboricity α of a graph is the number of forests it takes to cover all its edges. Being asymptotically related to the graph's degeneracy and maximal subgraph density, arboricity is considered a good measure of the sparsity of a graph.
Natural computational questions about arboricity include: computing the arboricity, obtaining a decomposition of the edges into few forests, and orienting the edges so that each vertex has only close to α out-edges.
In this talk, we will address these questions in the /dynamic/ setting, in which the graph is subject to arbitrary, adversarial insertions and deletions of edges.
We will see how maintaining an orientation with few out-edges from each vertex leads to efficient dynamic algorithms for matching, colouring, and decomposing into O(α) forests;
And we will see how to efficiently balance the number of out-edges in an orientation of the dynamic graph, via an almost local reconciliation between neighbouring vertices.

Date and Time: Nov 22, 2022, Tuesday, 13:00 CET

Speaker: Sanjeev Khanna, University of Pennsylvania

Host: Danupon Nanongkai, MPI-INF

Title: Sublinear Algorithms for Hierarchical Clustering

Abstract: Hierarchical clustering is a popular technique for organizing data as a rooted tree structure that simultaneously clusters data at multiple levels of granularity. A well-studied recent objective function views the input as a weighted graph with edges indicating similarity between the data points, and focuses on finding a tree that minimizes the cost of hierarchical partitioning. The resulting optimization problem is NP-hard, and previous algorithms for approximating this objective require at least linear time/space. In this talk, we will consider algorithms for hierarchical clustering that use sublinear resources (space, time, and communication). 

Specifically, we will present sublinear algorithms for hierarchical clustering in the streaming model (space), in the query model (time), and in the MPC model (communication). At the core of our algorithmic results is a connection between hierarchical clustering and a suitably relaxed notion of cut sparsifiers of graphs that lends itself to efficient sublinear algorithms. We complement our algorithmic results by establishing nearly matching lower bounds that rule out algorithms with better performance guarantees in each of these models.

This is joint work with Arpit Agarwal, Huan Li, and Prathamesh Patil.

Date and Time: Oct 25, 2022, Tuesday, 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 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.

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.