informatik-vortraege October 2023

informatik-vortraege@lists.rwth-aachen.de

3 participants
3 discussions

Einladung: Informatik-Oberseminar Henri Lotze

by Henri Lotze

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Montag, 13. November 2023, 09.30 Uhr Ort: Informatikzentrum, E3, 2. Etage, Raum 9222 Referent: Henri Lotze M.Sc. Lehr- und Forschungsgebiet Theoretische Informatik Thema: Going Offline -- Delays, Reservations and Predictions in Online Computation Abstract: The study of classical online computation builds upon a rather simple model. The input to a given problem is not known in advance, decisions have to made immediately upon the arrival of a new element and these decisions are irrevocable. While this model is very well suitable to compute worst case bounds to a broad range of problems, there are some problems which are not well suited for this analysis. Naturally, problems that do not admit a constant approximation ratio in their offline formulation do not admit a constant competitive ratio in the worst case in the online formulation. However, some problems that are approximable still do not admit a constant competitive ratio when analyzed in the online case. For a subset of these problems, such as the Online Simple Knapsack problem and the class of general F-Node- and F-Edge-Deletion problems, the reason for this seems to be that a single, specific bad decision by an algorithm can be arbitrarily punished by an adversary. In this talk, we explore modifications of the classical online model with the aim to find natural models that on the one hand cover a large range of problems and on the other hand work against pathological kinds of instances that restrict an algorithm from obtaining a constant competitive ratio. To this end, we study three modifications of the classical online model. The models that we study are that of "Late Accepts" -- with Advice --, which allows to postpone decisions in online minimization problems until a current partial solution does not uphold a certain property anymore. The second one is that of "Reservations", in which any decision may be postponed for a cost proportional to the gain of an item. Finally, the model of "Bounded Predictions" allows an online algorithm to see the complete instance in advance, with a caveat: There is noise on the instance -- controlled by an adversary -- and each element may actually deviate from its prediction, up to factor that is known to the algorithm. We are able to partially classify the advice complexity of the complete class of both F-Node-Deletion and F-Edge-Deletion problems. We give tight bounds on the competitive ratio for the Online Simple Knapsack problem with Reservations for the whole range of possible reservation costs, i.e. for a factor between 0 and 1. Finally, we give partially tight bounds for the Online Simple Knapsack problem with Bounded Predictions for the whole range of possible noise factors on the size of the items. Es laden ein: die Dozentinnen und Dozenten der Informatik

3 days, 6 hours

Re:

by Nagl, Manfred

Das war ein Fehlversuch. Sorry M. Nagl Von: Nagl, Manfred Gesendet: Mittwoch, 25. Oktober 2023 16:34 An: Vortraege(a)informatik.rwth-aachen.de Betreff: Prof. Dr.-Ing. Dr. h.c. Manfred Nagl, Emeritus Lehrstuhl Software Engineering RWTH Aachen University 52074 Aachen Tel. +49 241 8021350 Mobil +49 171 5463727

1 month, 2 weeks

Einladung: Informatik-Oberseminar Roman Matzutt

by Förster, Claudia

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 20. Oktober 2023, 15.30 Uhr Ort: Seminarraum Informatik 4 (COMSYS) - 9007, E3, Ahornstr. 55 [1] Digtaler Zugang (hybrider Vortrag): https://rwth.zoom-x.de/j/69772277508?pwd=SU5qN1FPVXI5V3UwakYydnBUUW1Ldz09 (Meeting-ID: 697 7227 7508 Kenncode: 031824) Referent: Roman Matzutt M.Sc. Lehrstuhl Informatik 4 (COMSYS) Thema: Demystifying and Adjusting the Promises of Blockchain-based Data Management in the Permissionless Setting Abstract: The digital currency Bitcoin introduced the blockchain as a data structure for establishing consensus in a decentralized manner. Since then, blockchain technology generalized to immutably recording arbitrary events and data, now allowing more general online interactions between distrusting users. This interaction model sparked a tremendous interest in blockchain technology, its potential, and applications. However, the identification of multiple shortcomings has since dampened this initial spirit of optimism. Our research focuses on deepening the understanding of these shortcomings, improving upon them, and gauging the true potential for blockchain-backed applications despite these limitations. We take a data-driven perspective to assess the security and longevity of permissionless blockchains, such as Bitcoin, where anybody can access the blockchain's full history and propose new data to be appended. Here, we identify two core challenges: First, the ability of malicious actors to irrevocably append illicit content to a blockchain implies required moderation capabilities despite the desired immutability. Second, the need for massively replicating the full and ever-growing blockchain history poses significant scalability challenges. We tackle these challenges with four contributions. First, we systematically analyze the phenomenon of blockchain content insertion, showing that inserting illicit content can create devastating consequences. Second, we explore means to mitigate these consequences by considering strategies to prevent content insertion and by proposing a new redactable blockchain for the swift and transparent removal of unwanted content. Third, we address the challenge of ever-growing blockchain sizes by proposing a gradually deployable block-pruning scheme that is retrofittable to Bitcoin and enables users to retroactively reduce their storage requirements. Finally, our fourth contribution shows that permissionless blockchains still hold an untapped potential for fueling novel applications by demonstrating how Bitcoin can help securely bootstrapping decentralized anonymity services. Overall, we shed new light on the potential impact of the data persisted on blockchains and widen the scope for resilient and durable blockchain designs for data management tasks. Es laden ein: die Dozentinnen und Dozenten der Informatik [1] https://www.comsys.rwth-aachen.de/fileadmin/misc/how-to-get-to-comsys.pdf

2 months

2023

2022

2021

2020

2019

2018

informatik-vortraege October 2023