Advanced search
Start date
Betweenand

Computational complexity and extremal combinatorics

Grant number: 18/05557-7
Support type:Scholarships in Brazil - Master
Effective date (Start): September 01, 2018
Effective date (End): August 31, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Cooperation agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
Principal researcher:Yoshiharu Kohayakawa
Grantee:Bruno Pasqualotto Cavalar
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated scholarship(s):18/22257-7 - Computational complexity and extremal combinatorics, BE.EP.MS

Abstract

This is the project for the master's degree of Bruno Pasqualotto Cavalar, to be developed under supervision of Y. Kohayakawa, at the Instituto de Matemática e Estatística, USP, from June 2018 to February 2020 (21 months). This project has as main focus the study of circuit complexity, in particular average-case monotone circuit complexity, and the interaction between the problems of these areas with results and methods of extremal combinatorics, such as the theory of random graphs. The project has as starting point works on monotone complexity developed by Razborov, Alon and Boppana, among others, as well as average-case results for monotone circuits developed by Rossman in distributions of random graphs.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications
(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)
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, . (19/13364-7, 18/05557-7, 18/04876-1)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
CAVALAR, Bruno Pasqualotto. Sunflowers theorems in computational complexity. 2020. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.