- Algoseminar - lists.rwth-aachen.de

Timeline Seminar Online Algorithms
by Matthias Gehnen 26 Jun '25

26 Jun '25

Dear Friends of Online Algorithms, In two weeks we will have our seminar about online algorithms, and you are warmly invited to attend at a subset of your choice as well. We will have one session with talks at each morning, and one with talks in the afternoon; with 1 h slots for each of the talks (so 35-45 minutes talk, ~15 minutes of questions, and time for a bathroom break). At noon, we will have a lunch break with sufficiently much time to go to the cafeteria or similar. Time Tuesday, 08.07 Wednesday, 09.07 Thursday, 10.07 09:00-10:00 Paging & List Accessing Christian Ricker Online Bin Packing Volodymyr Diemieniev Online Graph Coloring Joel Kollenberg 10:00-11:00 Online Knapsack with Advice Louis Thape The Reservation Settting Niklas Leinert Online Matching Tim Riedl 11:00-12:00 Randomization Daniel Lich k-Server Mira Brettmann Fractional VC & Matching Martin Clever 12:00-13:00 Lunch Break Lunch Break Lunch Break 13:00-14:00 Yao's Principle Raphael Rolland Online Scheduling Mustafa Al-Salhi Prediction in Graph Exploration Vincent Hollstein 14:00-15:00 Matroid Secretary Problem Jan Dornhege Algorithms with Predictions Jonathan Lyssy Tree Exploration Leonard Dicks 15:00-16:00 Secretary mit Advice Gabrijel Sokcevic Scheduling with Estimates Tom Hammel Quiz Session The talks will be held in room 4017 in the computer science building. Best and see you in two weeks then, Matthias

1 0

Talk by Lisa Wilhelmi
by Sukanya Pandey 28 May '25

28 May '25

Dear all, You are cordially invited to the virtual talk by Lisa Wilhelmi on 03.06.2025 at 14:00h. The title and abstract of the talk are as follows: ************************************************************************************************************************* Title: /Dynamic Debt Swapping in Financial Networks/ Abstract: A debt swap is an elementary edge swap in a directed, weighted graph, where two edges with the same weight swap their targets. Debt swaps are a natural and appealing operation in financial networks, in which nodes are banks and edges represent debt contracts. They can improve the clearing payments and the stability of these networks. However, their algorithmic properties are not well-understood. We analyze the computational complexity of debt swapping. Our main interest lies in semi-positive swaps, in which no creditor strictly suffers and at least one strictly profits. These swaps lead to a Pareto-improvement in the entire network. We consider network optimization via sequences of v-improving debt swaps from which a given bank v strictly profits. For ranking-based clearing, we show that every sequence of semi-positive v-improving swaps has polynomial length. In contrast, for arbitrary v-improving swaps, the problem of reaching a network configuration that allows no further swaps is PLS-complete. We identify cases in which short sequences of semi-positive swaps exist even without the v-improving property. *********************************************************************************************************************** You can attend the talk on zoom using the following link: Join Zoom Meeting https://rwth.zoom-x.de/j/67896818200?pwd=dnpeBlqJo9UE1vzxy2J9VcOlAzCG9b.1 <https://www.google.com/url?q=https://rwth.zoom-x.de/j/67896818200?pwd%3Ddnp…> Meeting ID: 678 9681 8200 Passcode: 642820 --- Join by SIP • 67896818200(a)lej.zmeu.us --- Join by H.323 • 159.124.47.249 (Germany) Meeting ID: 678 9681 8200 Passcode: 642820 Best regards, Sukanya -- Sukanya Pandey Postdoctoral Researcher Algorithms and Complexity Chair RWTH Aachen sukanyapandey.com

1 0

[adyn-talks] ADYN seminar: 02.06.2025, 17:00 CEST
by Tim Koglin 28 May '25

28 May '25

Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, June 2nd, 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) "The Offended Voter Model" by Marco Seiler (Goethe University Frankfurt) (2) "Designing Exploration Contracts" by Conrad Schecker (Goethe University Frankfurt) Abstracts: (1) In this talk we discuss a variant of the voter model on a coevolving network in which interactions of two individuals with differing opinions only lead to an agreement on one of these opinions with a fixed probability q. Otherwise, with probability 1-q, both individuals become offended in the sense that they never interact again, i.e. the corresponding edge is removed from the underlying network. Eventually, these dynamics reach an absorbing state at which there is only one opinion present in each connected component of the network. If globally both opinions are present at absorption we speak of "segregation", otherwise of "consensus'". We show that segregation and a weaker form of consensus both occur with positive probability for every q ∈ (0,1) and that the segregation probability tends to 1 as q → 0. Furthermore, we establish that, if q → 1 fast enough, with high probability the population reaches consensus while the underlying network is still densely connected. We briefly discuss results from simulations to assess the obtained results and to discuss further research directions. This talk is based on joint work with Raphael Eichhorn and Felix Hermann. (2) We propose a new model for contract design with sequential decision making where a principal delegates a search task to an agent. The agent sequentially explores n boxes, suffers an exploration cost for each inspected box, and selects the content (the "prize") of one inspected box as outcome. Agent and principal each obtain a value from the selected prize. To influence the search, the principal designs a contract with a non-negative payment to the agent for each potential prize. Her goal is to maximize her value minus payment. This natural contract scenario shares close relations to the classic Pandora's Box problem. We show how to compute optimal linear contracts in polynomial time. Moreover, we obtain efficient algorithms for optimal general contracts in several cases: When the agent has no individual value for prizes, when each box has only one prize with non-zero value for principal and agent, or for i.i.d. boxes with a single prize with positive value for the principal. This is joint work with Martin Hoefer and Kevin Schewior 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: 26.05.2025, 15:30 CEST (different time!)
by Tim Koglin 22 May '25

22 May '25

Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, May 26th, 15:30 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) "Prophet Inequalities with Minimal Priors" by Rebecca Reiffenhäuser (University of Amsterdam) (2) "Persuading Agents in Opinion Formation Games" by Tim Koglin (RWTH Aachen University) Abstracts: (1) Prophet Inequalities are a well-established paradigm in online optimization, but require knowledge of exact prior distributions. The talk will introduce and give an overview on some results that instead run on only a single sample per distribution, still achieving comparable, constant ratios. (2) Prominent opinion formation models such as the one by Friedkin and Johnsen (FJ) concentrate on the effects of peer pressure on public opinions. In practice, opinion formation is also based on information about the state of the world and persuasion efforts. In this talk, we will present an approach of Bayesian persuasion in the FJ model. There is an unknown state of the world that influences the internal beliefs of n agents. A sender S can (partially) reveal information about the state to all agents. The agents update their internal beliefs, and an equilibrium of public opinions emerges. We propose algorithms for the sender to reveal information in order to optimize various aspects of the emerging equilibrium. We will focus on a general class of range-based objectives based on desired opinion ranges for each agent. We will present efficient algorithms for the case that the matrix of internal beliefs in all states has constant rank. This generalizes, e.g., instances with a constant number of states and/or agents. This is joint work with Martin Hoefer and Tolga Tel. 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
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