Combinatória Assintótica com Aplicações em Teste de Propriedades e Estimação de Parâmetros.

• Processo: 15/15986-4
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de dezembro de 2015
• Data de Término da vigência: 29 de fevereiro de 2020
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Henrique Stagni
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM
• Bolsa(s) vinculada(s): 17/02263-0 - Teste de propriedades e estimação de parâmetros de grafos, BE.EP.DR
• Palavra(s)-Chave do Pesquisador: Objeto limite | Regularidade | teste de parâmetros | teste de propriedades | Combinatória e algoritmos

Resumo

Este projeto tem como foco o estudo assintótico de estruturas combinatórias por meio de técnicas como o Lema de Regularidade de Szemerédi e limite de sequências convergentes de grafos, com especial ênfase na aplicação de tais técnicas no contexto de teste de propriedades e estimação de parâmetros. O projeto tem como ponto de partida trabalhos sobre teste de propriedades e estimação de parâmetros desenvolvidos por Alon, Conlon, Fisher, Fox, Krivelevich, Newman, Shapira, dentre outros, que fazem uso de diversas variantes do Lema de Regularidade, assim como trabalhos sobre a teoria de seqüências convergentes de estruturas combinatórias, desenvolvidos por Borgs, Chayes, Lovász, Szegedy, dentre outros, que também possuem implicações na área de teste de propriedades e estimação de parâmetros. Objetivamos fazer contribuições aos métodos e às aplicações.

Publicações científicas

(4)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

HAN, J.; KOHAYAKAWA, Y.; SALES, M. T.; STAGNI, H.. ON SOME EXTREMAL RESULTS FOR ORDER TYPES. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, v. 88, n. 3, p. 779-785, 2019. (13/03447-6, 17/02263-0, 15/15986-4)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; LANG, RICHARD; LEFMANN, HANNO; STAGNI, HENRIQUE. ON THE QUERY COMPLEXITY OF ESTIMATING THE DISTANCE TO HEREDITARY GRAPH PROPERTIES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 2, p. 1238-1251, 2021. (17/02263-0, 15/15986-4, 18/04876-1)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; LANG, RICHARD; LEFMANN, HANNO; STAGNI, HENRIQUE. Estimating parameters associated with monotone properties. COMBINATORICS PROBABILITY & COMPUTING, v. 29, n. 4, p. 17-pg., 2020-07-01. (17/02263-0, 15/15986-4, 13/03447-6)

HAN, JIE; KOHAYAKAWA, YOSHIHARU; SALES, MARCELO TADEU; STAGNI, HENRIQUE; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Property Testing for Point Sets on the Plane. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 13-pg., 2018-01-01. (13/07699-0, 15/15986-4, 14/18641-5, 13/03447-6)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

STAGNI, Henrique. Teste de propriedades e estimação de parâmetros. 2020. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.