- Algoseminar - lists.rwth-aachen.de

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