- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Fall 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 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
- 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
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Speaker
Monday, December 11, 2023 - 15:45 to 16:45
Gates 122 and streaming via Zoom
Host:
Noah Stephens-Davidowitz
Categories:
Simple Circuit Lower Bound via Algorithm for the Range Avoidance Problem (via Zoom)
Abstract: We present a simple single-valued FS_2P algorithm for the Range Avoidance Problem. As a result, we obtain the circuit lower bound S_2E \not \subset i.o.-SIZE[2^n/n] and many other corollaries:
1.Almost-everywhere near-maximum circuit lower bound for Sigma_2E \intersect Pi_2E and for ZPE^NP.
2.Pseudodeterministic FZPP^NP constructions for: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and K^poly-random strings.
This talk is based on the following preprint: https://eccc.weizmann.ac.il/report/2023/156/.
Bio: Li Zeyong is a fourth-year PhD student from National University of Singapore, advised by Prof. Divesh Aggarwal. His research interest lies in, broadly speaking, theoretical computer science, slightly biased towards complexity/hardness related stuff. Currently he works on hardness of Lattice problems (lower bounds and algorithms, etc) and a bit of complexity theory.