Virtual Theory Seminar

Date and Time: August 10, 2023, Thursday, 16:00 CEST
Speaker : Euiwoong Lee, University of Michigan
Host : Danupon Nanongkai, MPI-INF
Title: Parameterized Approximability of F-Deletion Problems

Abstract: 

For a family F of graphs, the F-Deletion Problem asks to remove the minimum number of vertices from a given graph G to ensure that G belongs to F. One of the most common ways to obtain an interesting family F is to fix another family H of graphs and let F be the set of graphs that do not contain any graph H as some notion of a subgraph, including (standard) subgraph, induced subgraph, and minor.
This framework captures numerous basic graph problems, including Vertex Cover, Feedback Vertex Set, and Treewidth Deletion, and provides an interesting forum where ideas from approximation and parameterized
algorithms influence each other. In this talk, I will give a brief survey on the state of the art on the F-Deletion Problems for the above three notions of subgraphs, and talk about a recent result on Weighted Bond Deletion.

Date and Time: July 18, 2023, Tuesday, 13:00 CEST
Speaker: Michal Koucky, Charles University
Host: Tomasz Kociumaka, MPI-INF
Title: Locally consistent decomposition of strings with applications to edit distance sketching

Abstract:  

In this talk I will present a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness and ignoring poly-log factors). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ.
This decomposition has applications to edit distance sketching and streaming approximate pattern matching algorithms.

Joint work with Sudatta Bhattacharya.

Date and Time: April 20, 2023, Thursday, 13:00 CET
Speaker : Standa Zivny, University of Oxford, United Kingdom
Host : Daniel Marx, CISPA Helmholtz Center for Information Security
Title: Promise Constraint Satisfaction Problems

Abstract: 

I’ll introduce the area of promise constraint satisfaction and present a few recent results.

Date and Time: March 02, 2023, Thursday, 13:00 CET
Speaker : Seth Pettie, University of Michigan, USA
Host : Sebastian Brandt, CISPA Helmholtz Center for Information Security
Title: Optimal Vertex Connectivity Oracles

Abstract:

A vertex connectivity oracle is a data structure that answers queries of the form MIN{kappa(u,v), k}, where kappa(u,v) is the vertex connectivity between u and v, i.e., queries are answered precisely up to the threshold k. In this talk I'll prove an information-theoretic lower bound of Omega(kn) on the space complexity of vertex connectivity oracles. This bound is tight, up to logarithmic factors, and settles a long-standing question on whether vertex-connectivity is more complex than edge-connectivity. (The talk will take a tour through several erroneous theorems of Schnorr'79, Gusfield-Naor'90, and Benczur'95, who made the opposite claim, that vertex-connectivity information could be encoded in O(n log n) bits.) We also give an improvement to the Izsak-Nutov vertex connectivity oracle. It occupies space O(kn log n), answers queries in O(log n) time, and is constructible in the time of poly(k) maximum flows. Joint work with Thatchaphol Saranurak and Longhui Yin (STOC 2022). arXiv:2201.00408.

Date and Time: Feb 21, 2023, Tuesday, 13:00 CET
Speaker : Ryan Williams, MIT, USA,
Host : Markus Blaeser, Saarland University
Title: The Mystery of the Missing String

Abstract:

We reconsider the old question of what is the "smallest" complexity class containing a function of high circuit complexity. We show how to view this question and others in terms of a simple problem called Missing String: given a list of m strings of length n, with m < 2ⁿ, find a string not on the list. We show in multiple ways how algorithms for Missing String can translate directly into lower bounds, and vice-versa: lower bounds for Missing String can imply upper bounds of a certain form.

Based on a paper with Nikhil Vyas in ITCS'23.

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: Locality in online, dynamic, sequential, and distributed graph algorithms

Abstract:

I will discuss the notion of locality in the context of graph problems, from four different perspectives: online graph algorithms, dynamic graph algorithms, sequential distributed algorithms, and parallel distributed algorithms.

I will use the graph coloring problem as a running example, and I will explore settings like this:

- Online graph algorithms: The adversary reveals the graph one node at a time. How far do you need to see around a node until it is safe to pick its color?

- Dynamic graph algorithms: The adversary constructs the graph one edge at a time, and you need to maintain a valid coloring after each addition. How far around the new edge do you need to modify the solution?

- Distributed graph algorithms: Each node has to choose its own color simultaneously in parallel based on its local neighborhood. How far does it need to see?

While these are different questions in general, we can show that there are families of graph problems for which all these notions are equal to each other.

This talk is based on joint work with Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, and Joona Särkijärvi, and there is a manuscript available at https://arxiv.org/abs/2109.06593

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:

e 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.