+**********************************************************************
*
*
* 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
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
+**********************************************************************
*
*
* 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