- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Spring 2025 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University / Cornell Tech - High School Programming Workshop and Contest 2025
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Robotics Ph. D. prgram
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
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 with a 2^{\Omega_d(n)} additive gap between their depth-d and depth-(d+1) formula complexity.
Bio: I am a second-year PhD student studying Theoretical Computer Science at MIT advised by Ryan Williams. Before this, I was an undergraduate at Rutgers University, where I was lucky enough to discuss research and learn from Eric Allender and Michael Saks. I also participated twice in the DIMACS REU program.
Most of my research is in the field of Computational Complexity Theory, which quantifies the amount of resources — like time and hardware — needed to solve computational tasks, like finding the fastest route from point A to point B on a map.