Скачать или смотреть Two decades of property testing

Property Testing studies the design and analysis of algorithms that Test if some (massive) data satisfies some global Property without looking at all the data, or inferring the parameters that explain how the data satisfies the property. It was initiated by accidental discoveries, by Blum, Luby and Rubinfeld, and by Babai, Fortnow and Lund, showing that some complex properties could be tested remarkably efficiently.
In the near quarter-century since these discoveries, the scope of Property Testing has expanded broadly - it covers properties of algebraic, graph-theoretic, statistical, and functional nature; and the resulting techniques have connected the field to combinatorics, additive number theory, harmonic analysis, algebraic geometry while having applications in complexity theory, combinatorial optimization and even extremal graph theory.
In this talk I will look back at some of this history attempting to describe some of the diversity of the results and impact; and try to present a personal perspective, via "Invariance", that explains some of the reasons for the diversity, and tries to extract some coherent picture among this diversity.

Speaker: Madhu Sudan, Harvard University.

Workshop on Theoretical Computer Science 2016: https://cs.hse.ru/en/big-data/tcs-lab...
Faculty of Computer Science: https://cs.hse.ru/en/
Follow us:   / hsefcs  ,   / cs_hse