Property testing and estimation of graph parameters

Abstract

This is the research proposal for Henrique Stagni, doctoral student at the University of São Paulo, for FAPESP's internship abroad program Bolsa de Estágio de Pesquisa no Exterior (BEPE), to be conducted at Tel Aviv University, under the supervision of Professor Asaf Shapira. The goal of this project is the study of property testing and estimation of parameters of combinatorial structures. More specifically, our objective consists of getting better bounds on the number of vertices one needs to sample from a combinatorial structure in order to get a good approximation for a parameter of that structure. Professor Asaf Shapira has obtained striking results in the areas of extremal combinatorics and theoretical computer science, and is a leading expert in the area of property testing, a subject that he has worked on since his PhD thesis. Tel Aviv University (TAU) is a world center for combinatorics and theoretical computer science. Noga Alon, Baumritter Professor of Mathematics and Computer Science at TAU, is the senior member of the area there. Professor Shapira's colleagues include Michael Krivelevich and Wojciech Samotij, highly recognized researchers in the area. We are absolutely certain that the candidate and his doctoral project will greatly benefit from this internship. More broadly speaking, this internship also has the potential of having a substantial impact on the FAPESP Thematic Project Combinatorial structures, optimization, and algorithms in theoretical computer science (Proc. 2013/03447-6). (AU)