Property testing and parameter estimation (2020)
- Authors:
- Autor USP: STAGNI, HENRIQUE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: TEORIA DOS GRAFOS
- Keywords: Combinatorial types; Distância de edição; Edit distance; Erdos-Hajnal property; Estimação de parâmetros; Hereditary properties; Lemas de regularidade; Monotone properties; O-tipos; Order types; Parameter estimation; Property testing; Propriedade de Erdos-Hajnal; Propriedades hereditárias; Propriedades monótonas; Regularity lemmas; Speed of subgraph classes; Teste de propriedades; Tipos combinatórios; Velocidade de classes de grafos
- Agências de fomento:
- Language: Inglês
- Abstract: 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
- Imprenta:
- Data da defesa: 20.11.2020
-
ABNT
STAGNI, Henrique. Property testing and parameter estimation. 2020. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2020. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-11022021-194125/. Acesso em: 28 dez. 2025. -
APA
Stagni, H. (2020). Property testing and parameter estimation (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-11022021-194125/ -
NLM
Stagni H. Property testing and parameter estimation [Internet]. 2020 ;[citado 2025 dez. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-11022021-194125/ -
Vancouver
Stagni H. Property testing and parameter estimation [Internet]. 2020 ;[citado 2025 dez. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-11022021-194125/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
