23 maja 2023 14:29
Andrzej Pelc on Algorithms with advice 25.05.23 (sala 119, 12:30)
Na najbliższym seminarium ZZOiAA 25.05.23 (sala 119, 12:30) wystąpi Andrzej Pelc (Université du Québec en Outaouais, Kanada)
Tytuł wystąpienia: Algorithms with advice
Streszczenie
It is well known that getting additional information concerning parameters of
a problem can significantly reduce the complexity of its algorithmic solution.
In this talk we describe a paradigm that permits us to establish quantitatively
the tradeoff between the amount of information known to an algorithm solving
a given problem and its complexity. We consider an oracle knowing the entire
instance of a problem P, that can give advice to entities (such as nodes of
a network or mobile agents navigating in it) that execute an algorithm A solving P.
This advice is under the form of a binary string whose length is called the size
of advice. The entities learn the advice but do not know the instance. The oracle
cooperates with the algorithm that can interpret the obtained advice in the most
clever way. For a given problem P we ask the question what is the minimum size
of advice that permits to solve this problem with a given complexity. This minimum
size can be considered as a measure of difficulty of achieving this complexity in
a solution of P. In the talk we show the application of the advice paradigm to a large
variety of well-known problems.
Serdecznie zapraszamy!