Skip to main content
Search
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Image
Lower Bounds, Learning, and Average-Case Complexity
Program
Meta-Complexity
Date
Monday, Feb. 13
–
Friday, Feb. 17, 2023
Back to calendar
Breadcrumb
Home
Workshop & Symposia
Schedule
Secondary tabs
The Workshop
Schedule
Videos
Schedule Subject to Change; all times in PT
Eric Allender's Day
Monday, Feb. 13, 2023
9
–
9:25 a.m.
Coffee and Check In
9:25
–
9:30 a.m.
Opening Remarks
9:30
–
10:15 a.m.
A Commentary on the Collision of Worlds
Rahul Santhanam (Oxford)
Video
10:15
–
10:30 a.m.
Break
10:30
–
11:15 a.m.
Allender's Conjecture and its Impacts on Meta-Complexity
Shuichi Hirahara (National Institute of Informatics)
Video
11:15
–
11:30 a.m.
Break
11:30 a.m.
–
12:15 p.m.
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Rahul Ilango (MIT)
Video
12:15
–
2:15 p.m.
Lunch
2:15
–
3 p.m.
Improved Learning from Time-bounded Kolmogorov Complexity
Halley Goldberg (Simon Fraser University)
Video
3
–
3:25 p.m.
Break
3:25
–
4:10 p.m.
Journey with Eric Allender: From Turing Machines to Circuits, and Back
Michal Koucky (Charles University)
Video
4:10
–
4:30 p.m.
How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
Neekon Vafa (MIT)
Video
4:30
–
5:30 p.m.
Reception
Tuesday, Feb. 14, 2023
9
–
9:30 a.m.
Coffee and Check In
9:30
–
10:15 a.m.
The Mystery of the Missing String
Ryan Williams (MIT)
Video
10:15
–
10:30 a.m.
Break
10:30
–
11:15 a.m.
A Combinatorial Characterization of Minimax in 0/1 Games
Shay Moran (Technion)
Video
11:15
–
11:30 a.m.
Break
11:30 a.m.
–
12:15 p.m.
Replicability in Learning
Jessica Sorrell (UCSD)
Video
12:15
–
2:15 p.m.
Lunch
2:15
–
3 p.m.
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Hanlin Ren (University of Oxford)
Video
3
–
3:30 p.m.
Break
3:30
–
4:15 p.m.
Quantum Learning Algorithms Imply Circuit Lower Bounds
Alex Grilo (CNRS/Sorbonne Université)
Video
Wednesday, Feb. 15, 2023
9
–
9:30 a.m.
Coffee and Check In
9:30
–
10:15 a.m.
Learning Versus Pseudorandom Generators in Constant Parallel Time
Mikito Nanashima (Tokyo Institute of Technology)
Video
10:15
–
10:30 a.m.
Break
10:30
–
11:15 a.m.
A Duality Between One-Way Functions and Average-Case Symmetry of Information
Zhenjian Lu (University of Oxford)
Video
11:15
–
11:30 a.m.
Break
11:30 a.m.
–
12:15 p.m.
Quantum Meets Minimum Circuit Size Problem
Nai-Hui Chia (Rice University)
Video
12:15
–
2:15 p.m.
Lunch
2:15
–
3 p.m.
Learning Safe Action Models
Brendan Juba (Washington University in St. Louis)
Video
3
–
3:30 p.m.
Break
3:30
–
4:15 p.m.
New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method
Lijie Chen (MIT)
Video
Thursday, Feb. 16, 2023
9
–
9:30 a.m.
Coffee and Check In
9:30
–
10:15 a.m.
Succinct Neural Networks
Adam Kalai (Microsoft Research)
Video
10:15
–
10:30 a.m.
Break
10:30
–
11:15 a.m.
New Approaches to Heuristic Pac-learning vs. PRFs
Ari Karchmer (Boston University)
Video
11:15
–
11:30 a.m.
Break
11:30 a.m.
–
12:15 p.m.
On the Average-case Complexity of the Nearest Boolean Vector to a Subspace
Andrej Bogdanov (University of Ottawa)
Video
12:15
–
2:15 p.m.
Lunch
2:15
–
3:15 p.m.
Average-case Complexity for Polynomials, and All That
Emanuele Viola (Northeastern University)
Video
3:15
–
3:30 p.m.
Break
3:30
–
4:15 p.m.
On Low End Obfuscation and Learning
Gal Yehuda (Technion)
Video
Friday, Feb. 17, 2023
9
–
9:30 a.m.
Coffee and Check In
9:30
–
10:15 a.m.
Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
Yanyi Liu (Cornell)
Video
10:15
–
10:30 a.m.
Break
10:30
–
11:15 a.m.
What (Doesn't) Make Learning Algorithms Generalize?
Roi Livni (Tel Aviv University)
Video
11:15
–
11:30 a.m.
Break
11:30 a.m.
–
12:15 p.m.
Learning with Distributional Inverters
Marco Carmosino (IBM Research)
Video
12:15
–
2:15 p.m.
Lunch
2:15
–
3 p.m.
Unstructured Hardness to Average-Case Randomness
Roei Tell (Institute for Advanced Study)
Video
Share this page
Copy URL of this page
link to homepage
Close
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
link to homepage
Close
Search