Meta-Complexity as the Bridge Between Learning and Cryptography, 2025

EnCORE Workshop at UCSD
San Diego, USA, 3-7 February 2025

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 92093

The 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.

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