Average-case hardness in proof complexity

• Grant number: 23/13743-3
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: December 13, 2023
• End date: March 12, 2024
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Théo Borém Fabris
• Supervisor: Susanna Figueiredo de Rezende
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Institution abroad: Lund University, Lund, Sweden
• Associated to the scholarship: 22/09280-5 - Probabilistic methods in computational complexity and geometry, BP.IC

Abstract

This is the research proposal of Théo Borém Fabris, 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 Lund University under the supervision of Professor Susanna Figueiredo de Rezende. The aim of this project is to study average-case lower bounds in restricted proof systems, such as Resolution and its variants, making use of probabilistic tools and combinatorial methods. (AU)