- 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
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs (via Zoom)
Abstract: Understanding the behavior of multi-player games under parallel repetition is an important problem in theoretical computer science. The parallel repetition conjecture by Feige and Lovasz claims that for every game with value less than 1, its parallel repetition value goes down exponentially fast in the number of repetition. While the conjecture is known to be true for all 2-player games (Raz '98), and a restricted family called connected games (Dinur, Harsha, Venkat, and Yuen '17), for every other multi-player game only inverse-Ackerman bounds are known (Verbitsky '96). I will talk about some recent progress on this problem, where we prove that for any 3-player game over binary inputs, the value of the parallel repetition decays at least polynomially fast. Specifically, I will present the proofs for the family of games where the 3 players receive inputs of Hamming weight 1, and among them, a particularly interesting game called Anti-Correlation Game for which we obtain an exponential bound. These proofs used completely new ideas compared to all previous results on parallel repetition. This is based on joint works with Uma Girish, Kunal Mittal, Justin Holmgren and Ran Raz.
Bio: Wei Zhan is a Ph.D student in the theory group of the Department of Computer Science at Princeton University, advised by Prof. Ran Raz. His research interest lies in complexity theory, quantum computation and boolean function analysis.