Informatics Colloquium 20. 12. Permutations - quasirandomness and property testing
Informatics Colloquium 20. 12. 2016, 14:00 posluchárna D2
prof. Daniel Kráľ, Department of Computer Science, University of Warwick
Permutations - quasirandomness and property testing
Abstract: The theory of combinatorial limits offers analytic tools to represent
and analyze large discrete objects. In the talk, we first present a
self-contained introduction to the theory and we then focus on three
applications concerning large permutations. The first is a characterization of
quasirandom permutations by pattern densities, which resolves a question of
Graham. The second is the permutation analogue of the result of Erdos, Lovasz
and Spencer on the independance of densities of subgraphs. This result is then
used in the third application, which concerns property and parameter testing
algorithms, i.e., algorithms that provides a correct answer based on a small
random sample of their input with high probability.