Computational complexity and extremal combinatorics

• Grant number: 18/22257-7
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: January 03, 2019
• End date: July 02, 2019
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Bruno Pasqualotto Cavalar
• Supervisor: Benjamin Rossman
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Institution abroad: University of Toronto (U of T), Canada
• Associated to the scholarship: 18/05557-7 - Computational complexity and extremal combinatorics, BP.MS

Abstract

This is the research proposal of Bruno Pasqualotto Cavalar, student at the University of São Paulo, for the FAPESP program Bolsa Estágio de Pesquisa no Exterior (BEPE), to be conducted at the University of Toronto, under the supervision of Professor Benjamin Rossman. The aim of this project is to study average-case lower bounds in restricted classes of Boolean circuits, such as monotone circuits and bounded-depth circuits, making use of combinatorial methods. (AU)

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)

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)