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

Testing and Streaming algorithms for words, trees and graphs
Saint Petersburg / spring 2019, посмотреть все семестры

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

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.

Date and time Class|Name Venue|short Materials
24 May
Лекция, Lecture ПОМИ РАН video
24 May
Лекция, Lecture ПОМИ РАН video