Skip to main content
Search
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
Main navigation
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
Participate
Apply to Participate
Propose a Program
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
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
News & Videos
News
Videos
Support for the Institute
Annual Fund
All Funders
Institutional Partnerships
For Visitors
Visitor Guide
Plan Your Visit
Location & Directions
Accessibility
Building Access
IT Guide
About
Image
Meta-Complexity Reunion
Program
Meta-Complexity
Location
Calvin Lab Auditorium
Date
Monday, Apr. 15
–
Thursday, Apr. 18, 2024
Back to calendar
Breadcrumb
Home
Workshop & Symposia
Schedule | Meta-Complexity Reunion
Secondary tabs
The Workshop
Schedule
Monday, Apr. 15, 2024
10
–
10:30 a.m.
Coffee and Check-in
10:30
–
11 a.m.
Beating Brute Force Search for Compression Problems
Ryan Williams (Massachusetts Institute of Technology)
11
–
11:30 a.m.
Break
11:30
–
12:30 a.m.
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle
Rahul Ilango (MIT)
12:30
–
2 p.m.
Lunch (on your own)
2
–
2:30 p.m.
Planted Clique Conjectures are Equivalent
Shuichi Hirahara (National Institute of Informatics, Tokyo)
2:30
–
3 p.m.
One Way Functions and Zero Knowledge
Mikito Nanashima (Tokyo Institute of Technology)
3
–
3:30 p.m.
Break
3:30
–
4 p.m.
Partial Minimum Branching Program Size Problem is ETH-hard
Ludmila Glinskih (Boston University)
4
–
4:30 p.m.
Every Optimal Circuit for Parity Partitions into a Binary Tree
Marco Carmosino (IBM)
4:30
–
5:30 p.m.
Reception
Tuesday, Apr. 16, 2024
9:30
–
10 a.m.
Coffee and Check-in
10
–
11 a.m.
TFNP and Cryptography: An Interplanetary Tour of Impagliazzo's Worlds
Daniel Mitropolsky (Columbia University)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12:30 p.m.
Kolmogorov comes to Cryptomania
Marshall Ball (NYU)
12:30
–
2 p.m.
Lunch (on your own)
2
–
3 p.m.
On SNARGs, Propositional Proofs, and Local Satisfiability
Alex Lombardi (Princeton University)
3
–
3:30 p.m.
Break
3:30
–
4:30 p.m.
A Direct PRF Construction from Kolmogorov Complexity
Yanyi Liu (Cornell University)
Wednesday, Apr. 17, 2024
9:30
–
10 a.m.
Coffee and Check-in
10
–
11 a.m.
Meta-Mathematics of Complexity Theory
Igor Carboni Oliveira (University of Warwick)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12 p.m.
A Feasibly Constructive Proof of the Schwartz-Zippel Lemma
Albert Atserias (UPC Barcelona)
12
–
12:30 p.m.
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Iddo Tzameret (Imperial College London)
12:30
–
2 p.m.
Lunch (on your own)
2
–
3 p.m.
PPP is Not Turing-Closed in the Black Box Setting
Robert Robere (McGill University)
3
–
3:30 p.m.
Break
3:30
–
4 p.m.
Quantum Automating TC⁰-Frege Is LWE-Hard
Noel Arteche (Lund University)
Thursday, Apr. 18, 2024
9:30
–
10 a.m.
Coffee and Check-in
10
–
11 a.m.
Polynomial-time Pseudo-deterministic Construction of Primes
Hanlin Ren (University of Oxford)
11
–
11:30 a.m.
Break
11:30 a.m.
–
12:30 p.m.
New Circuit Lower Bounds Via Solving Range Avoidance
Lijie Chen (UC Berkeley)
12:30
–
2 p.m.
Lunch (on your own)
2
–
3 p.m.
Strong vs. Weak Range Avoidance and the Linear Ordering Principle
Oliver Korten (Columbia University)
3
–
3:30 p.m.
Break
3:30
–
4 p.m.
Opening up the Distinguisher
Roei Tell (University of Toronto)
4
–
4:30 p.m.
Boosting Simple Learners Smoothly
Russell Impagliazzo (UC San Diego)
Share this page
Copy URL of this page
link to homepage
Close
Main navigation
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
Participate
Apply to Participate
Propose a Program
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
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
News & Videos
News
Videos
Support for the Institute
Annual Fund
All Funders
Institutional Partnerships
For Visitors
Visitor Guide
Plan Your Visit
Location & Directions
Accessibility
Building Access
IT Guide
About
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
link to homepage
Close
Search