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

(5)

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

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. LATIN 2020: THEORETICAL INFORMATICS, v. 12118, p. 12-pg., 2020-01-01. (18/05557-7, 18/22257-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)

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)

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.