• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2020.tde-11022021-194125
Documento
Autor
Nombre completo
Henrique Stagni
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2020
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Krauskopf, Marcos Abraham Kiwi
Mota, Guilherme Oliveira
Santos, Tássio Naia dos
Título en inglés
Property testing and parameter estimation
Palabras clave en inglés
Combinatorial types
Edit distance
Erdos-Hajnal property
Hereditary properties
Monotone properties
Order types
Parameter estimation
Property testing
Regularity lemmas
Speed of subgraph classes
Resumen en inglés
A graph property P is said to be testable with sample complexity q(\eps) if, for every \eps>0, there is a randomized decision algorithm that distinguishes objects satisfying P from graphs ``\eps-far'' from satisfying P, after inspecting a sample of size at most q(\eps) of the input graph G (in particular, the sample size does not depend on |V(G)|). Although the set of testable graph properties is now well understood, results for general properties P tipically rely on variants of Szemerédi's regularity lemma, giving tower-type upper bounds for the sample complexity q(\eps). Therefore, current research in the area is focused on obtaining better bounds for the sample complexity required to test specific properties P. A (normalized) graph parameter f is said to be estimable with sample complexity q(\eps) if, for every \eps>0, there is a randomized algorithm that estimates the parameter f(G) up to an additive error of \eps, after inspecting a sample of size at most q(\eps) of the input G. If the graph parameter being estimated is the distance \dP to a graph property P, Fischer and Newman proved that \dP is estimable for every testable P, but their proof provides a tower-type upper bound for estimating \dP, even if P can be efficiently testable. This thesis focuses on getting better upper bounds for the sample complexity required to estimate certain parameters and test certain properties. Our first contribution states that one can test the property of having a partition of size k with any given prescribed pairwise densities with a sample complexity polynomial in \eps^ and k. This result, which improves upon a previous (exponential in k) bound given by Goldreich, Goldwasser and Ron (1998), is an important tool for achieving our other contributions. Our main contribution shows that if a hereditary property P is testable with sample complexity q(\eps), then distance \dP is estimable with sample complexity at most exponential in q(\eps). In particular, for hereditary properties P known to be be efficiently testable, our method provides much better bounds than the ones relying on Szemerédi's regularity lemma. Our techniques also allow one to get more reasonable bounds for estimating other graph parameters. We also prove negative results about testing graph properties described by linear constraints of subgraph densities, which were considered by Goldreich and Shinkar (2016). We conclude this thesis by proving bounds for the complexity of testing that every hereditary property of configurations of points in the plane is testable.
Título en portugués
Teste de propriedades e estimação de parâmetros
Palabras clave en portugués
Distância de edição
Estimação de parâmetros
Lemas de regularidade
O-tipos
Propriedade de Erdos-Hajnal
Propriedades hereditárias
Propriedades monótonas
Teste de propriedades
Tipos combinatórios
Velocidade de classes de grafos
Resumen en portugués
Uma propriedade P de grafos é testável com complexidade amostral q(\eps) se, para todo \eps>0, existe um algoritmo aleatorizado que distingue grafos que satisfazem P de grafos ``\eps-longe'' de a satisfazer P, após inspecionar uma amostra de tamanho no máximo q(\eps) do grafo de entrada G (em particular, o tamanho da amostra independe de |V(G)|). Apesar do conjunto de propriedades testáveis ter sido completamente caracterizado, resultados gerais sobre testabilidade costumam se basear em variantes do lema da regularidade de Szemerédi e dão cotas superiores do tipo torre de exponenciais para q(\eps). Portanto, a pesquisa na área tem se concentrado em obter melhores cotas para a complexidade amostral para se testar certas propriedades P. Um parâmetro (normalizado) de grafo f é estimável com complexidade amostral q(\eps) se, para todo \eps>0, existe um algoritmo aleatorizado que computa f(G), a menos de um erro aditivo de \eps, após inspecionar uma amostra de tamanho no máximo q(\eps) do grafo de entrada G. Se o parâmetro em questão é a distância \dP a uma propriedade P, Fischer e Newman (2007) provaram que \dP é estimável para toda propriedade testável P. Contudo, o método deles fornece uma cota do tipo torre, mesmo para propriedades P que podem ser eficientemente testadas. O objetivo desta tese é fornecer melhores cotas superiores para a complexidade amostral para estimar certos parâmetros e testar certas propriedades. Nossa primeira contribuição afere que é possível testar se um grafo admite uma partição de tamanho k com densidades pré-especificadas entre pares de partes com complexidade amostral polinomial em \eps e k. Esse resultado, que representa uma melhora em relação à cota exponencial em k obtida por Goldreich, Goldwasser e Ron (1998), é essencial para a obtenção de nossas outras contribuições. Nossa principal contribuição afere que se uma propriedade hereditária P é testável com complexidade amostral q, então \dP é estimável com complexidade amostral apenas exponencial em q. Em particular, para propriedades hereditárias P que podem ser eficientemente testáveis, nosso método fornece cotas melhores do que as baseadas no lema da regularidade de Szemerédi. As técnicas empregadas também nos permitem obter cotas mais razoáveis para estimar outros parâmetros de grafos. Provamos também resultados negativos a respeito de propriedades consideradas por Goldreich e Shinkar (2016), descritas por restrições lineares das densidades de subgrafos. Concluímos a tese mostrando que propriedades hereditárias de configurações de pontos no plano são testáveis.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
tese.pdf (1.48 Mbytes)
Fecha de Publicación
2021-02-16
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.