- Diversity, Equity, and Inclusion
- Research News
- Department Life
- Oral History of Cornell CS
- CS 40th Anniversary Booklet
- ABC Book for Computer Science at Cornell by David Gries
- Department Timeline
- Job Postings
- Ithaca Info
- Internal info
- Graduation Information
- Cornell Tech Colloquium
- Student Colloquium
- Fall 2023 Colloquium
- Conway-Walker Lecture Series
- Salton Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University High School Programming Contests 2023
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop
Worst-Case to Average-Case Reductions via Additive Combinatorics (via Zoom)
Abstract: We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides a transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O-tilde(T) that are correct on all inputs.
Using our framework, we obtain efficient worst-case to average-case reductions for fundamental problems in a variety of computational models: algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems.
Our techniques rely on results from additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma.
To appear in STOC 2022.
Bio: Igor Shinkar is an Assistant Professor in the School of Computing Science at Simon Fraser University. He received his PhD in 2014 from Weizmann Institute of Science in Israel. Igor is broadly interested in theoretical computer science, discrete mathematics, probability, and the interplay between them.