- Algoseminar - lists.rwth-aachen.de

Talk
by Martin Hoefer 07 May '25

07 May '25

Dear all - Jana Nickel will give a talk about Game Theory from a category theoretical perspective on May 15, 2025 at 3pm in the i1 seminar room (4017). Looking forward to seeing you there, Martin

1 0

Bachelor's thesis talk by Leander Besting
by Sukanya Pandey 22 Apr '25

22 Apr '25

Dear all, You are cordially invited to the Bachelor's thesis talk of Leander Besting on 28.04.2025 at 14:00h in Seminar room of I1. The title and the abstract of the talk are as follows: *************************************************************************************************************************** Title: /Claims Trading for Least Clearing States in Financial Networks /Abstract:/ /The notion of a claims trade, within the financial network model of Eisenberg and Noe [1], was introduced in a recent paper by Hoefer, Ventre and Wilhelmi [2]. It studies how the legal framework of Chapter 11 bankruptcy, particularly a creditor’s ability to sell claims, can be used to stabilize a financial network from within, avoiding external, especially governmental, involvement. In this thesis we consider the novel approach of judging a claims trade’s effect based on the least clearing state and not the greatest, which is typically considered for Eisenberg-Noe networks. The least clearing state represents the outcome of a decentralized clearing process, rather than a centralized one. To this end, we introduce a new clearing algorithm. Unlike most previous algorithms, ours computes the least clearing state. Additionally it works on all common types of payment strategies and even possible combinations of these, where previous algorithms only worked for one specific type of strategy. Afterwards, we look at the previous methods for finding optimal claims trades. We give pathological examples, showing that they cannot be adapted to the least clearing state, and then discuss intuitions for why they behave differently in this scenario. This is followed by a new algorithm for finding optimal claims trades, w.r.t. the least clearing state. Our claims trading algorithm works on the same strategy profiles as our clearing algorithm. In particular, this covers all payment strategies for which claims trading algorithms are known w.r.t. the greatest clearing state. **************************************************************************************************************************** Best regards, Sukanya -- Sukanya Pandey Postdoctoral Researcher Algorithms and Complexity Chair RWTH Aachen sukanyapandey.com

1 0

[adyn-talks] ADYN seminar: 07.04.2025, 17:00 CEST
by Tim Koglin 02 Apr '25

02 Apr '25

Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, April 7th, 17:00 CEST*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "Constraint Satisfaction Problems with Advice" by Suprovat Ghoshal (Indiana University) (2) "A Combinatorial Approach to Chernoff Bounds" by William Kuszmaul (Carnegie Mellon University) Abstracts: (1) We initiate the study of algorithms for Constraint Satisfaction Problems (CSPs) with ML oracle advice. We introduce two models of advice and then design approximation algorithms for several fundamental CSPs, such as Max Cut, Max 2-Lin, and Max 3-Lin in these models. In particular, we show the following. 1. For Max-Cut and Max 2-Lin, we design an algorithm that yields near-optimal solutions when the average degree is larger than a threshold degree, which only depends on the amount of advice and is independent of the instance size. We also give an algorithm for nearly satisfiable Max 3-Lin instances with quantitatively similar guarantees. 2. Further, we provide impossibility results for algorithms in these models. In particular, under standard complexity assumptions, we show that Max 3-Lin is still $1/2 + \eta$ hard to approximate given access to advice, when there are no assumptions on the instance degree distribution. Additionally, we also show that Max 4-Lin is $1/2 + \eta$ hard to approximate even when the average degree of the instance is linear in the number of variables. This is joint work with Konstantin Makarychev and Yury Makarychev. (2) - For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim

1 0

[adyn-talks] ADYN seminar: 31.03.2025, 17:00 CET
by Tim Koglin 28 Mar '25

28 Mar '25

Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, March 31st, 17:00 CET*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "Naively Sorting Evolving Data is Optimal and Robust" by George Giakkoupis (Inria Centre at Rennes University) (2) "Fast Self-Stabilizing Ranking" by Thorsten Götte (Hamburg University) Abstracts: (1) In the evolving sorting problem, introduced by Anagnostopoulos, Kumar, Mahdian and Upfal (2011), the true ranking changes while the sorting algorithm is processing the input. More precisely, each comparison operation of the algorithm is followed by a sequence of evolution steps, where an evolution step perturbs the true rank of a random item by a "small" random value. The goal is to maintain an ordering that remains close to the true ranking over time. I will present a very simple sorting algorithm, which samples a random pair of adjacent items in each step and swaps them if they are out of order. The algorithm achieves and maintains, with high probability, optimal total deviation, $O(n)$, and optimal maximum deviation, $O(log n)$, under very general model assumptions. G. Giakkoupis, M. Kiwi and D. Los. Naively sorting evolving data is optimal and robust. Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 2217-2242, 2024. (2) We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common task. We are given $n$ anonymous agents, and the goal is to assign each agent a unique rank in $\{1, \dots, n\}$. Given unique ranks, it is straightforward to select a designated leader. Thus, our protocol is a self-stabilizing leader election protocol as well. Ranking requires at least $n$ states per agent; hence, the goal is to minimize the additional number of states, called overhead states. The core of our protocol is a space-efficient but non-self-stabilizing ranking protocol that requires only $n + O(\log n)$ states. Our protocol stabilizes in $O(n^2\ log n)$ interactions w.h.p. and in expectation, using $n + O(\log^2 n)$ states in total. Our stabilization time is asymptotically optimal. In comparison to the currently best known ranking protocol by Burman et al. [PODC ‘21], which requires $n + \Omega(n)$ states, our result exponentially improves the number of overhead states. Please note that the following session will already take place one week later on April 7th. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim

1 1

Seminar Talks at I7
by Pandey, Sukanya 14 Feb '25

14 Feb '25

Dear all, We would like to bring to your attention the following talks organised by I7, which you may interesting. Talk1 Speaker: Anna Limbach (Czech Academy of Sciences) Title: Graphon Branching Processes and Fractional Isomorphism Time: Thursday, February 20, 10am Place: Seminar room i7 Talk 2 Speaker: Benny Kimelfeld (Technion) Title: tba Time: Friday, February 21, 10:30am Place: Seminar room i7 Best regards, Sukanya

1 0

[adyn-talks] ADYN seminar: 03.02.2025, 17:00 CET
by Tim Koglin 29 Jan '25

29 Jan '25

Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, February 3rd, 17:00 CET*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "A New Look on an Old Counter Example of Doeblin Measures" by Noam Berger Steiger (Technical University of Munich) (2) "Noisy Linear Group Testing: Exact Thresholds and Efficient Algorithms" by Olga Scheftelowitsch (TU Dortmund University) Abstracts: (1) We consider an example from 2017 of a Doeblin function that admits two extremal Doeblin measures, and see that's variants thereof provide counter examples to a number of conjectures, in particular we get a non-mixing Doeblin measure, and Doeblin functions that admit Doeblin measures of different entropies. I will start by giving a thorough introduction to the topic of Doeblin functions and measures. Based on an old work with Hoffman and Sidoravicius, and a new work with Conache, Johansson and Öberg. (2) In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability α, independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants c such that cnlogn tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim

1 0

[adyn-talks] ADYN seminar: 13.01.2025, 17:00 CET
by Tim Koglin 08 Jan '25

08 Jan '25

Dear all, happy new year to everyone! The DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, January 13th, 17:00 CET*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "Chromatic Number of Randomly Augmented Graphs" by Anand Srivastav (Kiel University) (2) "Insights into (k, ρ)-Shortcutting Algorithms" by Alexander Leonhardt (Goethe University Frankfurt) Abstracts: (1) An extension of the Erdős-Renyi random graph model $G_{n,p}$ is the model of perturbed graphs introduced by Bohman, Frieze and Martin (2003). This is a special case of the randomly augmented graphs studied in this paper. An augmented graph is the union of a deterministic host graph and a random graph. Among the first problems in perturbed graphs has been the question how many random edges are needed to ensure Hamiltonicity of the graph. This question was answered in the paper by Bohman, Frieze and Martin. The host graph is often chosen to be a dense graph. In recent years several papers on combinatorial functions of perturbed graphs were published, e.g. on the emergence of powers of Hamiltonian cycles (Dudek, Reiher, Ruciński, Schacht 2020), the properties of Positional Games played on perturbed graphs (Clemens, Hamann, Mogge, Parczyk, 2020) and the emergence of multiple invariants e.g. fixed clique size (Bohman, Frieze, Krivelevich, Martin, 2004). In this paper we study the chromatic number of randomly augmented graphs. We concentrate on a host graph $H$ with chromatic number $o(n)$, augmented by a $G_{n,p}$ with $n^{-\frac{1}{3} + \delta}\leq p(n) \leq 1-\delta$ for some $\delta \in (0,1)$. We denote such a graph by $\pert_{H,p}$. Our main result is an upper bound for the chromatic number of such a randomly augmented graph $\pert_{H,p}: we show that for any $\epsilon>0$ there is a $n(\epsilon) \in \N$ such that for $n \geq n(\epsilon)$ with high probability $\chromaticOf{\pert_{H,p}} \leq (1+o(1)) \cdot \frac{n \log(b)}{2 (\log(n) - \log(\chromaticOf{H}))}$. This result collapses to the famous theorem of Bollobás (1988), when $H$ is the empty host graph, thus our result can be regarded as a generalization of the latter. Our proof is not constructive. To give the reader an impression of a coloring strategy, we give a constructive proof of the upper bound for the chromatic number of $\pert_{H,p}$ where the chromatic number of the host grah is at most $\frac{n}{\log(n)^{\alpha}}$ where $\alpha>\frac{1}{2}$. (2) A graph is called a (k, ρ)-graph iff every node can reach ρ of its nearest neighbors in at most k hops. This property has proven useful in the analysis and design of parallel shortest-path algorithms [Blelloch et al., 2016; Dong et al., 2021]. Any graph can be transformed into a (k, ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate shortcut set of minimal cardinality. We show that kρ-MSP is NP-complete in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a related construction, we bound the approximation factor of known kρ-MSP heuristics [Blelloch et al., 2016] from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) that optimally solves kρ-MSP. Finally, we compare the practical performance and quality of all algorithms empirically. This is joint work with Manuel Penschuck and Ulrich Meyer. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim

1 0

ADYN seminar
by Pandey, Sukanya 12 Dec '24

12 Dec '24

Dear all, Please find below the invitation from the DFG Research unit ADYN for their online seminar. Best, Sukanya -------- Forwarded Message -------- Subject: ADYN seminar: 16.12.24, 17:00 CET Date: Thu, 12 Dec 2024 10:08:18 +0100 From: koglin(a)cs.uni-frankfurt.de<mailto:koglin@cs.uni-frankfurt.de> To: adyn-talks(a)cs.uni-frankfurt.de<mailto:adyn-talks@cs.uni-frankfurt.de> Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on * Monday, December 16th, 17:00 CET * Access via ZOOM: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "A Strongly Polynomial Algorithm for The Minimum-Cost Generalized Flow Problem" by Lázló Végh (University of Bonn) (2) "Claims Trading with Default Costs" by Lars Huth (RWTH Aachen University) Abstracts: (1) We give a strongly polynomial algorithm for minimum cost generalized flow and, as a consequence, for all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent ‘subspace layered least squares’ interior point method, an earlier joint work with Allamigeon, Dadush, Loho and Natura. They show that the number of iterations needed by the IPM can be bounded in terms of the `straight line complexity’ of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. Our main contribution is a combinatorial analysis showing that the straight-line complexity of any minimum cost generalised flow instance is polynomial in the number of arcs and vertices. This is joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura, and Neil Olver. (2) In the Eisenberg-Noe model, a model for debt between financial institutions and quantifying systemic risk, there are n banks represented by nodes in a directed graph. Directed edges represent debt claims, and edge weights are liabilities. Each bank can use incoming payments to clear its debt. Moreover, each bank has a non-negative amount of external assets, which can also be used for payment of claims. With this talk, I will convey basic intuitions for problems in the model, specifically claims trades. In claims trades, there is a bank v in distress and a trading partner w. The latter is taking over some claims of v and in return giving liquidity to v. The idea is to rescue v (or mitigate contagion effects from v’s insolvency). We focus on the impact of trading claims fractionally, i.e. when v and w can agree to trade only part of a claim. This is joint work with Martin Hoefer and Lisa Wilhelmi. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ Best, Tim

1 0

Talk-Prof.Daniel Schmand
by Sukanya Pandey 05 Dec '24

05 Dec '24

Dear subscriber, We cordially invite you to the first talk of our group seminar. Please find the details below. *Date & Time: *Wednesday, 11th December at 14.00 hours *Location: *Seminar room I1 (Room 4017, E1) *Speaker: *Prof. Daniel Schmand *Topic: *"Solving Gerhard Woeginger's Hiking Problem" Best regards, Sukanya (on behalf of the Algorithms and Complexity Chair)

1 1