Property testing and parameter testing for permutations

Autor(es)

Hoppen, Carlos ; Kohayakawa, Yoshiharu ; Moreira, Carlos Gustavo ; Sampaio, Rudini Menezes ; SIAM/ACM

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS; v. 135, p. 2-pg., 2010-01-01.

Resumo

There has been peat interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size These problems ale called property testing and parameter testing, where a property or parameter is said to be testable if it, can be estimated accurately in this way The algorithmic appeal is evident. as, conditional on sampling, this leads to reliable constant-time randomized estimators Our paper addresses property testing and parameter testing for pet mutations in a subpermutation perspective, more precisely. we investigate permutation propel ties and parameters that, can be well-approximated based on randomly chosen subpermutations of much smaller size In this context, we give a permutation counterpart, of a famous result by Alon and Shapna [6] stating that every hereditary graph property is testable Moreover, we develop a. theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al [12] in the case of graphs This theory is interesting lot its own sake. as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in [0,1](2), which in turn may be used to define a new model of tandom permutations (AU)

• Processo FAPESP: 07/56496-3 - A análise de estruturas discretas de grandes proporções
• Beneficiário: Carlos Hoppen
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático