City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Seminar on Computer Science
Saint Petersburg / autumn 2019, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Abstract of first seminar:

In this talk, I outline the notion of local checkability and point at various ways this has proven useful. Local checking (or local verification, or local decision, or local detection, or...) and locally checkable predicates (or languages, or labeling, or ...) were suggested (by Afek, K., and Yuvan, 1990) in the context of self-stabilization. The motivation was the easy detection that program malfunctions so that it can be restarted. It was contrasted with the costly (i.e. global) checking suggested by Katz and Perry.

It was pointed out that this notion also resembles easy checking (or decision, or ...), i.e. polynomial vs. costly computing. Indeed, the use of this notion has spread beyond self-stabilization to various fields such as (distributed) complexity theory, distributed testing and peer to peer computing.

Открытый семинар по всем областям Computer Science. Если вы хотели бы выступить на семинаре, напишите, пожалуйста, Александру Куликову.

Date and time Class|Name Venue|short Materials
26 September
18:30–19:50
Impacts of Local Checkability, Lecture ПОМИ РАН No