The main open question of meta-complexity is to determine the algorithmic complexity of the following problem: What is the circuit (time-bounded Kolmogorov) complexity of a given string? After over fifty years, it is still not known if this problem is in P, or is NP-complete. Understanding the complexity of this problem turns out to be crucial also for cryptography (the existence of one-way functions) and computational learning (Valiant's PAC learning model).
This workshop will bring together researchers in meta-complexity, cryptography and learning to discuss recent progress, identify the next research goals, and start new collaborations on the promising research directions. Our focus will be on the connections between cryptography and learning, with meta-complexity as the bridge between the two areas.
In addition to regular research talks, we have tutorials and an open problems' session, and will also dedicate a significant amount of time for informal discussions among the participants. Participation in the workshop is by invitation only.
Schedule
Day One: Monday, Feb 3
| 10:30AM | Check-In And Coffee |
|---|---|
| 11:00AM | Tutorial: The Power of Distinguishing Simple From Complex Marco Carmosino |
| 11:30AM | |
| 12:00PM | |
| 12:30PM | LUNCH (on own) |
| 1:00PM | |
| 1:30PM | |
| 2:00PM | Tutorial: One-Way Functions and Kolmogorov Complexity Yanyi Liu |
| 2:30PM | |
| 3:00PM | |
| 3:30PM | Break |
| 4:00PM | On the NP-Completeness of GapMCSP and Indistinguishability Obfuscation Noam Mazor |
| 4:30PM | |
| 5:00PM | Universal Extrapolation Mikito Nanashima |
| 5:30PM | Welcome Reception |
| 6:00PM |
Day Two: Tuesday, Feb 4
| 10:30AM | Check-In And Coffee |
|---|---|
| 11:00AM | Tutorial: Frontiers of Efficient PAC Learning Rocco Servedio |
| 11:30AM | |
| 12:00PM | |
| 12:30PM | LUNCH (on own) |
| 1:00PM | |
| 1:30PM | |
| 2:00PM | Tutorial: Smoothed Boosting Applied to the Theory of Cryptography Russell Impagliazzo |
| 2:30PM | |
| 3:00PM | |
| 3:30PM | Break |
| 4:00PM | Towards Tractable Fragments for Skolem Synthesis Brendan Juba |
| 4:30PM | Open problems session |
| 5:00PM | |
| 5:30PM |
Day Three: Wednesday, Feb 5
| 10:30AM | Check-In And Coffee |
|---|---|
| 11:00AM | Is it (NP) hard to distinguish order from chaos? Rahul Ilango |
| 11:30AM | |
| 12:00PM | Reverse Mathematics of Complexity Lower Bounds Lijie Chen |
| 12:30PM | Afternoon Activity |
| 1:00PM | |
| 1:30PM | |
| 2:00PM | |
| 2:30PM | |
| 3:00PM | |
| 3:30PM | |
| 4:00PM | |
| 4:30PM |
Day Four: Thursday, Feb 6
| 10:30AM | Check-In And Coffee |
|---|---|
| 11:00AM | On White-Box Learning and Public-Key Encryption Yanyi Liu |
| 11:30AM | |
| 12:00PM | Toward Witness Encryption via NP-hardness of PAC Learning Halley Goldberg |
| 12:30PM | Lunch (on own) |
| 1:00PM | |
| 1:30PM | |
| 2:00PM | Synergy between Circuit Obfuscation and Circuit Minimization Ilya Volkovich |
| 2:30PM | |
| 3:00PM | Learning vs the Deletion Channel Rik Sengupta |
| 3:30PM | Break |
| 4:00PM | Is nasty noise actually harder than malicious noise? Rocco Servedio |
| 4:30PM | |
| 5:00PM | Discussion |
| 5:30PM |
Day Five: Friday, Feb 7
| 10:30AM | Check-In And Coffee |
|---|---|
| 11:00AM | Private PAC Leaning may be harder than Online Learning Rathin Desai |
| 11:30AM | Discussion |
| 12:00PM | |
| 12:30PM | Lunch (on own) |
| 1:00PM | |
| 1:30PM |
Contributed Talks
Participants wishing to speak at the workshop on any topic related to meta-complexity, learning theory, or cryptography are invited to submit an Extended Abstract of up to three pages (including references) in at least 10pt font by email to the organizers, via email to Valentine Kabanets, describing the content of the contributed presentation.
We encourage the submission of abstracts on work at all levels of progress, including already published results, work in progress, novel contributions, as well as survey-type contributions. Early-stage work emphasizing connections between meta-complexity, learning, and cryptography is strongly encouraged.
Depending on the number of submissions, contributed talks will be 30 or 50 minutes long. A collection of abstracts of all invited and contributed talks will be posted at the workshop website.
Logistics
Location
We are hosted by the Institute for Emerging CORE Methods in Data Science (EnCORE) at University of California San Diego, on the 4th floor of Atkinson Hall. The address is:
3235 Voigt Dr, La Jolla, CA 92093The recommended rideshare drop-off location is Parking Lot P503. Please do not park in this parking lot as you will likely be ticketed and/or towed.
Parking
UCSD offers both metered spaces and permit-only parking lots. Parking can be limited, so we encourage the use of public transportation when possible.
- Visitor Parking Information (how to pay)
- UCSD parking maps
- Accessible parking (for visitors with a Disabled Person placard or license plate)
The Hopkins Parking Structure is located at 10100 Hopkins Dr., La Jolla, CA 92093. Please allow 20-30 minutes to park and walk to the event venue.
Lodging
Attendees can book a nearby AirBnB, or the closest hotels are:
Organizers
- Marco L. Carmosino, IBM
- Russell Impagliazzo, UCSD
- Valentine Kabanets, SFU
- Antonina Kolokolova, MUN