BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-11589@webedit.cs.cornell.edu
DTSTAMP:20210419T200000Z
DTSTART:20210419T200000Z
DTEND:20210419T210000Z
SUMMARY:Towards Hardness for the Minimum Circuit Size Problem
DESCRIPTION:Rahul Ilango, Massachusetts Institute of Technology. Towards Hardness for the Minimum Circuit Size Problem (via Zoom)Abstract: Understanding the computational complexity of the Minimum Circuit Size Problem (MCSP) is a longstanding goal in theoretical computer science, dating back to at least the 1950s. In particular, it is a major open problem to show MCSP is intractable under standard (worst-case) complexity assumptions. Moreover, this question has gained renewed importance as researchers have discovered connections between MCSP and a growing number of fields, including cryptography, learning theory, and average-case complexity. In this talk, I will briefly recap some of this context for research on MCSP and then overview recent joint works that prove hardness results for several natural variants of MCSP, including versions for constant depth formulas and partial functions. Finally, I will end by highlighting an application of our techniques which establishes the existence of functions...https://webedit.cs.cornell.edu/content/towards-hardness-minimum-circuit-size-problem
LOCATION:Streaming via Zoom
END:VEVENT
END:VCALENDAR