- About
- Events
- Calendar
- Graduation Information
- Cornell Tech Colloquium
- Student Colloquium
- BOOM
- Spring 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2023 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University - High School Programming Contests 2024
- 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
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- 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
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Speaker
Thursday, February 23, 2017 - 16:15 to 18:00
G01 Gates Hall - Mentor's Lecture Hall
Host:
Bobby Kleinberg
Categories:
Computational complexity theory is rooted in many of computer science's most fascinating questions.Three examples of such questions are: Are there functions that are simple to describe, and yet require large circuits to compute? Are there short mathematical theorems that require lengthy proofs? Does every efficient randomized algorithm have an efficient deterministic counterpart?
In this talk I will describe results motivated by and contributing to our understanding of these questions, focusing on three results:
(1) An average-case depth hierarchy theorem for boolean circuits, which resolves a thirty-year-old conjecture in circuit complexity;
(2) Exponentially-improved lower bounds for the Frege proof system, the canonical proof system for propositional logic;
(3) The fastest deterministic algorithm for finding satisfying assignments of CNF formulas that have many such assignments, a basic unresolved problem in derandomization.
These results highlight rich connections among the respective subfields of complexity theory --- circuit complexity, proof complexity, and pseudorandomness --- and also have implications to areas outside of complexity theory, such as parallel computing and SAT solving. I will also touch on how the techniques we have developed point to avenues for progress on a few flagship challenges of complexity theory.
Bio:
Li-Yang Tan received a PhD in Computer Science from Columbia University in 2014. From 2014 to 2015 he was a Microsoft Research fellow at the UC Berkeley Simons Institute for the Theory of Computing, and since 2015 he has been a research assistant professor at the Toyota Technological Institute in Chicago. His research interests are in computational complexity, with an emphasis on circuit complexity, proof complexity, pseudorandomness, and the analysis of boolean functions. He is a recipient of the Best Paper award at FOCS '15 and an NSF Algorithmic Foundations (Medium) award.