slideshow 3

Complexity seminar

Some Results in Property Testing

Alexander Belov
University of Latvia

 

Friday, 20. December 2019 - 13:30 to 15:00

in IM, rear building, ground floor

The field of property testing deals with the following question. Given an object, detect whether it satisfies some property or is far from doing so. Usually, the object is modelled as a bit-string, and the distance is (relative) Hamming distance. The goal is to develop an algorithm whose complexity is very small: much smaller than the size of the object.