Computational complexity and extremal combinatorics

• Grant number: 18/05557-7
• Support Opportunities: Scholarships in Brazil - Master
• Start date: September 01, 2018
• End date: August 31, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Bruno Pasqualotto Cavalar
• Host 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.

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, 2021. (19/13364-7, 18/05557-7, 18/04876-1)

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

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.