|Когда:||Пятница, 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.