Busca avançada
Ano de início
Entree

Complexidade computacional e combinatória extremal

Processo: 18/05557-7
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de setembro de 2018
Situação:Interrompido
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Convênio/Acordo: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Pesquisador responsável:Yoshiharu Kohayakawa
Beneficiário:Bruno Pasqualotto Cavalar
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):18/22257-7 - Complexidade computacional e combinatória extremal, BE.EP.MS
Assunto(s):Combinatória   Teoria dos grafos   Métodos probabilísticos   Grafos aleatórios

Resumo

Este é o projeto de pesquisa para o mestrado de Bruno Pasqualotto Cavalar, a ser desenvolvido sob a supervisão de Y. Kohayakawa, no Instituto de Matemática e Estatística, USP, no período de 1/6/2018 a 29/02/2020 (21 meses) Este projeto tem como foco o estudo de complexidade de circuitos, em especial a complexidade de caso médio de circuitos monótonos, e a interação dos problemas dessas áreas com técnicas e resultados de combinatória extremal, como a teoria de grafos aleatórios. O projeto tem como ponto de partida os trabalhos sobre complexidade monótona desenvolvidos por Razborov e Alon e Boppana, dentre outros, bem como os resultados no caso médio para circuitos monótonos desenvolvidos por Rossman em distribuições de grafos aleatórios.