- 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, September 23, 2024 - 15:45 to 16:45
Gates 114 and streaming (via Zoom)
Host:
Eshan Chattopadhyay
Categories:
Title: On the Existence of Seedless Condensers: Exploring the Terrain
This joint work with Eshan Chattopadhyay and Mohit Gurumukhani is to appear in FOCS’24.
Abstract: While the existence of randomness extractors has been thoroughly studied, very little is known regarding the existence of seedless condensers. We prove several new results regarding seedless condensers for three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF sources, and almost Chor-Goldreich (CG) sources. These sources are a sequence of random variables over many symbols. There are l symbols out of which g symbols are "good", and the remaining "bad" symbols adversarially depend on the good symbols. The difference between each of these sources is realized by restrictions on the power of the adversary.
The following are our main results:
• When g <= l/2, for all three classes of sources, condensing above rate 1/floor(l/g) is impossible. In fact, this is tight for online NOSF sources and uniform almost CG sources.
• For g > l/2, we show the existence of excellent condensers for online NOSF sources. In contrast, we show that non-trivial condensing (above the input rate g/l) is impossible for NOSF sources for all g, l, obtaining a separation between NOSF and online NOSF sources.
Bio: Noam (Nomi) Ringach is a third year PhD in CS at Cornell University advised by Eshan Chattopadhyay. He is broadly interested in pseudorandomness and complexity theory with a current love for condensers, extractors, expanders, and codes. His recent work focuses on constructing condensers for adversarial sources and (two-sided) lossless expanders. In his free time, he enjoys baking, rock climbing, and hiking.