Advanced search
Start date
Betweenand

Computational complexity and extremal combinatorics

Grant number: 18/22257-7
Support type:Scholarships abroad - Research Internship - Master's degree
Effective date (Start): January 03, 2019
Effective date (End): July 02, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Yoshiharu Kohayakawa
Grantee:Bruno Pasqualotto Cavalar
Supervisor abroad: Benjamin Rossman
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Local de pesquisa : 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.