IME-USP

Property testing and parameter estimation

Defesa de Doutorado  
Nome: Henrique Stagni
Orientador: Prof. Dr. Yoshiharu Kohayakawa
Título:  Property testing and parameter estimation
Data: 20/11/2020
Horário: 16h00
Link para transmissão ao vivo: https://meet.google.com/aer-tvsv-pfw
Resumo:  STAGNI, H. Property testing and parameter estimation 2020. 88 f. Thesis (Doctorate) – Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2020. A graph property P is said to be testable with sample complexity q(ε) if, for every ε > 0, there is a randomized decision algorithm that distinguishes objects satisfying P from graphs “ε-far” from satisfying P, after inspecting a sample of size at most q(ε) 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 [AFNS09, BCL+08], results for general properties P tipically rely on variants of Szemerédi’s regularity lemma [Sze78], giving tower-type upper bounds for the sample complexity q(ε). 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(ε) if, for every ε > 0, there is a randomized algorithm that estimates the parameter f(G) up to an additive error of ε, after inspecting a sample of size at most q(ε) of the input G. If the graph parameter being estimated is the distance dP to a graph property P, Fischer and Newman [FN07] 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 ε −1 and k. This result, which improves upon a previous (exponential in k) bound given in [GGR98], 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(ε), then distance dP is estimable with sample complexity at most exponential in q(ε). 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 in [GS16]. 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. Keywords: property testing, parameter estimation, edit distance, speed of subgraph classes, monotone properties, hereditary properties, regularity lemmas, order types, combinatorial types, Erdős–Hajnal property

Data

20/11/2020
Expired!

Tempo

04:00 - 19:00
Categoria