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 plan to have some 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.

Tutorial Speakers

Schedule

To Be Announced

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 MAILTO-LINK-HERE, 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 15-30 minutes long. A collection of abstracts of all invited and contributed talks will be posted at the workshop website.

Logistics

Organizers