Asymptotic Combinatorics with Applications in Property Testing and Parameters Estimation.

• Grant number: 15/15986-4
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: December 01, 2015
• End date: February 29, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Henrique Stagni
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM
• Associated scholarship(s): 17/02263-0 - Property testing and estimation of graph parameters, BE.EP.DR

Abstract

The object of this project is the asymptotic study of combinatorial structures, using techniques such as Szemerédi's Regularity Lemma and limits of convergent graph sequences, with special emphasis on the application of such techniques in the areas of property testing and parameter estimation. The project has as starting point the work on property testing and parameter estimation developed by Alon, Conlon, Fisher, Fox, Krivelevich, Newman, Shapira, among others, which makes use of several variants of the regularity lemma, as well as the theory of convergent sequences of combinatorial structures, developed by Borgs, Chayes, Lovász, Szegedy, among others, which also has consequences in the area of property testing and parameter estimation. We aim at making contributions to the methods and to the applications.

Scientific publications

(4)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

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)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

STAGNI, Henrique. Property testing and parameter estimation. 2020. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.