Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Пятница, 24 мая 2019, 19:30–21:00
Где: ПОМИ РАН

Описание

Abstract: A tester is a randomized algorithm which distinguishes between a structure which satisfies a property and a structure which is far from satisfying the property, with few queries (constant, or sublinear). Examples: Testing if a function is linear, if a word follows a regular expression, a tree satisfies a DTD, a graph is 3-colorable.

Streaming algorithms read a stream of data and decide a property without storing the entire data. We will mention the classical examples and study in particular the detection of clusters in a stream of graph edges. Streaming testers are testers and streaming algorithms.

Видео