Letter from the Director, January 2023

Dear friends,

Greetings from Berkeley. I hope 2023 is off to a great start for you.

To kick off the new year, we’ve relaunched our Simons Institute website with an updated look and feel. Please take a look and let us know what you think.

We congratulate Simons Institute Associate Director Sandy Irani for recently being named an ACM fellow! ACM bestowed this honor on her for her “contributions to the theory of online algorithms and quantum complexity theory.”

This semester, the Simons Institute is hosting a program on Meta-Complexity, a topic that has witnessed intense activity and remarkable progress in recent years. Meta-complexity concerns the computational complexity of problems that are themselves about computational models. A quintessential problem is the minimum circuit size problem (MCSP), which asks for the smallest circuit to realize an input function, given its truth table specification. One natural focus of the subject is to study the complexity of such meta-complexity problems themselves (for instance, an outstanding question is whether MCSP is NP-complete). 

In addition, an exciting aspect has been the development of meta-complexity tools to attack foundational questions in cryptography, learning theory, and proof complexity. These extraneous applications are especially striking because the statements established do not concern meta-complexity, and yet the proofs rely on meta-complexity in a fundamental way.

The program is bringing together a large number of researchers, including several graduate students and junior researchers, spanning computational complexity, logic, proof complexity, cryptography, and learning theory, for a concerted, in-depth study of the big challenges concerning meta-complexity and its many connections. A big welcome to everyone, old and new friends!

In our SimonsTV corner this month, we’re featuring three tutorial videos from our recent Meta-Complexity Boot Camp: a presentation by Valentine Kabanets on the Power of Distinguishing Simple From Random; and a talk by Rahul Ilango on the Quest for Hardness of Meta-Complexity: Progress, Barriers, and Next Steps; and a presentation by Rafael Pass on Cryptography and Kolmogorov Complexity.

Finally, a great thank you to those who contributed to our first annual fund campaign. We truly rely on our partnership with you, our community, to be able to continue to deliver the scientific content and environment that make up the Simons Institute.

In closing, I wish to encourage us all to reflect on how scientific philanthropy can change lives. I am in awe (again) by the vision of Jim and Marilyn Simons in “providing a life line” to Ukrainian scientists.

Best regards,
Shafi

Shafi Goldwasser
Director, Simons Institute for the Theory of Computing