Proving the Minimum Formula Size Problem is ETH-Hard 🔍
Join Rahul Ilango from MIT as he explores why the Minimum Formula Size Problem remains computationally hard under ETH assumptions, shedding light on fundamental challenges in discrete mathematics and theoretical computer science.
Institute for Advanced Study
1.1K views • Mar 7, 2022
About this video
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.
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.
Video Information
Views
1.1K
Likes
32
Duration
01:14:03
Published
Mar 7, 2022
User Reviews
4.5
(1) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
Trending Now