Workshops

Spring 2023

Lower Bounds, Learning, and Average-Case Complexity

Feb 13, 2023 to Feb 17, 2023

Return to event »

Monday, February 13th, 2023
9:00 am–9:25 am		Coffee and Check In
9:25 am–9:30 am		Opening Remarks
9:30 am–10:15 am		A Commentary on the Collision of Worlds Rahul Santhanam (Oxford)
10:15 am–10:30 am		Break
10:30 am–11:15 am		Allender's Conjecture and its Impacts on Meta-Complexity Shuichi Hirahara (National Institute of Informatics)
11:15 am–11:30 am		Break
11:30 am–12:15 pm		NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach Rahul Ilango (MIT)
12:15 pm–2:15 pm		Lunch
2:15 pm–3:00 pm		Improved Learning from Time-bounded Kolmogorov Complexity Halley Goldberg (Simon Fraser University)
3:00 pm–3:25 pm		Break
3:25 pm–4:10 pm		Journey with Eric Allender: From Turing Machines to Circuits, and Back Michal Koucky (Charles University)
4:10 pm–4:30 pm		How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP) Neekon Vafa (MIT)
4:30 pm–5:30 pm		Reception

Tuesday, February 14th, 2023
9:00 am–9:30 am		Coffee and Check In
9:30 am–10:15 am		The Mystery of the Missing String Ryan Williams (MIT)
10:15 am–10:30 am		Break
10:30 am–11:15 am		Extending Generalization Theory Towards Addressing Modern Challenges in Machine Learning Shay Moran (Technion)
11:15 am–11:30 am		Break
11:30 am–12:15 pm		Replicability in Learning Jessica Sorrell (UCSD)
12:15 pm–2:15 pm		Lunch
2:15 pm–3:00 pm		Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms Hanlin Ren (University of Oxford)
3:00 pm–3:30 pm		Break
3:30 pm–4:15 pm		Quantum Learning Algorithms Imply Circuit Lower Bounds Alex Grilo (CNRS/Sorbonne Université)

Wednesday, February 15th, 2023
9:00 am–9:30 am		Coffee and Check In
9:30 am–10:15 am		Learning Versus Pseudorandom Generators in Constant Parallel Time Mikito Nanashima (Tokyo Institute of Technology)
10:15 am–10:30 am		Break
10:30 am–11:15 am		A Duality Between One-Way Functions and Average-Case Symmetry of Information Zhenjian Lu (University of Oxford)
11:15 am–11:30 am		Break
11:30 am–12:15 pm		Quantum Meets Minimum Circuit Size Problem Nai-Hui Chia (Rice University)
12:15 pm–2:15 pm		Lunch
2:15 pm–3:15 pm		Learning Safe Action Models Brendan Juba (Washington University in St. Louis)
3:15 pm–3:30 pm		Break
3:30 pm–4:15 pm		New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method Lijie Chen (MIT)

Thursday, February 16th, 2023
9:00 am–9:30 am		Coffee and Check In
9:30 am–10:15 am		Succinct Neural Networks Adam Kalai (Microsoft Research)
10:15 am–10:30 am		Break
10:30 am–11:15 am		New Approaches to Heuristic PAC-learning via Cryptanalysis Ari Karchmer (Boston University)
11:15 am–11:30 am		Break
11:30 am–12:15 pm		On the Average-case Complexity of the Nearest Boolean Vector to a Subspace Andrej Bogdanov (University of Ottawa)
12:15 pm–2:15 pm		Lunch
2:15 pm–3:15 pm		Average-case Complexity for Polynomials, and All That Emanuele Viola (Northeastern University)
3:15 pm–3:30 pm		Break
3:30 pm–4:15 pm		On Low End Obfuscation and Learning Gal Yehuda (Technion)

Friday, February 17th, 2023
9:00 am–9:30 am		Coffee and Check In
9:30 am–10:15 am		Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity Yanyi Liu (Cornell)
10:15 am–10:30 am		Break
10:30 am–11:15 am		What (Doesn't) Make Learning Algorithms Generalize? Roi Livni (Tel Aviv University)
11:15 am–11:30 am		Break
11:30 am–12:15 pm		TBA Marco Carmosino (IBM Research)
12:15 pm–2:15 pm		Lunch
2:15 pm–3:00 pm		Unstructured Hardness to Average-Case Randomness Roei Tell (Institute for Advanced Study)