Complexidade computacional e combinatória extremal

• Processo: 18/05557-7
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2018
• Data de Término da vigência: 31 de agosto de 2020
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Acordo de Cooperação: 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
• Palavra(s)-Chave do Pesquisador: combinatória | Complexidade Computacional | Grafos Aleatórios | Métodos Probabilísticos | Problemas extremais | teoria dos grafos | Complexidade Computacional

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.

Publicações científicas

(5)

(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)

CAVALAR, BRUNO PASQUALOTTO; KUMAR, MRINAL; ROSSMAN, BENJAMIN. Monotone Circuit Lower Bounds from Robust Sunflowers. LATIN 2020: THEORETICAL INFORMATICS, v. 12118, p. 12-pg., 2020-01-01. (18/05557-7, 18/22257-7)

CAVALAR, BRUNO PASQUALOTTO; KUMAR, MRINAL; ROSSMAN, BENJAMIN. Monotone Circuit Lower Bounds from Robust Sunflowers. ALGORITHMICA, v. 84, n. 12, p. 31-pg., 2022-07-14. (18/22257-7, 18/05557-7)

BARROS, GABRIEL FERREIRA; CAVALAR, BRUNO PASQUALOTTO; KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME OLIVEIRA; NAIA, TASSIO. DIRECTED GRAPHS WITH LOWER ORIENTATION RAMSEY THRESHOLDS. RAIRO-OPERATIONS RESEARCH, v. 58, n. 4, p. 13-pg., 2024-09-09. (18/05557-7, 18/04876-1, 20/16570-4, 19/13364-7, 19/04375-5)

BARROS, G. F.; CAVALAR, B. P.; MOTA, G. O.; PARCZYK, O.. Anti-Ramsey Threshold of Cycles for Sparse Graphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 10-pg., 2019-08-30. (18/04876-1, 18/05557-7)

BARROS, GABRIEL FERREIRA; CAVALAR, BRUNO PASQUALOTTO; KOHAYAKAWA, YOSHIHARU; NAIA, TASSIO. ORIENTATION RAMSEY THRESHOLDS FOR CYCLES AND CLIQUES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 4, p. 2844-2857, 2021. (19/13364-7, 18/05557-7, 18/04876-1)

Publicações acadêmicas

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

CAVALAR, Bruno Pasqualotto. Teoremas de girassol em complexidade computacional. 2020. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.