Proving the Minimum Formula Size Problem is ETH-Hard 🔍

Computer Science/Discrete Mathematics Seminar I Topic: The Minimum Formula Size Problem is (ETH) Hard Speaker: Rahul Ilango Affiliation: Massachusetts Institute of Technology Date: March 7, 2022 Understanding the complexity of the Minimum Circuit Size Problem (MCSP) is a longstanding mystery in theoretical computer science. Despite being a natural problem about circuits (given a Boolean function's truth table, determine the size of the smallest circuit computing it), answers to basic questions about MCSP still elude us (for example, is it NP-hard?). This mystery is compounded by recent work showing intriguing connections between basic questions about MCSP and open problems in a growing number of areas, including cryptography, average-case complexity, and learning theory. In this talk, I will review this background and motivation (no prior knowledge on MCSP required) and then discuss work that builds towards basing the intractability of MCSP on standard worst-case assumptions. More specifically, in the latter part I will talk about how one can show the "formula version" of MCSP (the Minimum Formula Size Problem) is not in P if the Exponential Time Hypothesis holds.