Métodos probabilísticos em complexidade computacional e geometria

• Processo: 22/09280-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2022
• Data de Término da vigência: 31 de julho de 2024
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Théo Borém Fabris
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Bolsa(s) vinculada(s): 23/13743-3 - Cotas inferiores para o caso médio em complexidade de prova, BE.EP.IC
• Assunto(s): Geometria Complexidade computacional Grafos aleatórios Teoria dos grafos Métodos probabilísticos
• Palavra(s)-Chave do Pesquisador: Aprendizado PAC | Complexidade Computacional | Geometria | Grafos Aleatórios | Métodos Probabilísticos | teoria dos grafos | Combinatória e complexidade computacional

Resumo

Este é o projeto de pesquisa para a iniciação científica de Théo Borém Fabris, a ser desenvolvido sob a supervisão de Y. Kohayakawa, no Instituto de Matemática e Estatística, USP, no período de 01/10/2022 a 30/09/2023 (12 meses). Este projeto tem como principal objetivo um estudo aprofundado, em nível de graduação, de técnicas que utilizam a teoria de probabilidade para resolver problemas oriundos de outras áreas da matemática e ciência da computação. Este trabalho envolverá o estudo de técnicas probabilísticas aplicadas a áreas diversas, como combinatória, teoria dos números, complexidade computacional e geometria. O estudo e implementação de uma construção elementar de grafos expansores estão também previstos. Um dos objetivos maiores do projeto é assegurar que o candidato obtenha uma formação mais profunda em certas áreas da matemática e computação não normalmente cobertas pelas disciplinas de graduação, a fim de que ele possa ingressar posteriormente num programa de pós-graduação já com preparação específica avançada.(AU)