News and events archive
From the faculty
Informatics Colloquium 20. 12. Permutations - quasirandomness and property testingInformatics 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.