News

In the opening talk from the Simons Institute’s recent workshop on Online and Matching-Based Market Design, Paul Milgrom (Stanford) introduced fast approximation algorithms for the knapsack problem that have no confirming negative externalities, and guarantee close to 100% for both allocation and investment.

In her Richard M. Karp Distinguished Lecture, Monika Henzinger (Institute of Science and Technology Austria) surveyed the state of the art in dynamic graph algorithms, the different algorithmic techniques developed for them, and all the questions in the field that still await an answer.

The Simons Institute for the Theory of Computing has received a $300,000 grant from the UC Noyce Initiative to hold a research program on Cryptography in Summer 2025, and a Department of Energy sub-award of $1.2 million in support of the Institute’s Research Pod in Quantum Computing.

The theorem goes by many names, as researchers have discovered and rediscovered it in different contexts. Some call it the experts’ theorem: for example, given two recommendations from two experts to buy two different stocks, the theorem lays out a method to combine the two recommendations that will perform almost as well as the best of these two experts. For this story, we will call it Blackwell’s approachability theorem — to highlight David Blackwell, the UC Berkeley mathematician who proved it and published it in 1956.

Simons Foundation International (SFI) has awarded a $25 million matching pledge to the Simons Institute for the Theory of Computing at the University of California, Berkeley, to build an ongoing stream of philanthropic revenue that will support the mission and research of the Institute.

Dear friends,

Greetings from Berkeley. At the Simons Institute, we are halfway through a vibrant semester of research and discovery. At the same time, like many of you, I am troubled and deeply saddened this week by the news of the enormous suffering and loss of life in Israel and Gaza. The series of devastating earthquakes in Afghanistan is also heartwrenching. I’m pleased to share news from the Institute with you, but must also acknowledge that all this is happening amidst a lot of turmoil elsewhere in the world. 

Is ingesting in-copyright works posted on the open internet as training data for building large language models copyright infringement or not? The stakes for this nascent industry and for researchers in the resolution of this issue could not be greater. Presented by Pamela Samuelson (Berkeley Law) as part of the Simons Institute’s workshop on Large Language Models and Transformers.

On the first day of the workshop on Large Language Models and Transformers, Alexei Efros (UC Berkeley) moderated a panel that addressed a range of topics, including the future of LLMs, memorization vs. generalization, and novelty and creativity. Featuring Sanjeev Arora (Princeton University), Chris Manning (Stanford), Yejin Choi (University of Washington), Ilya Sutskever (OpenAI), and Yin Tat Lee (University of Washington and Microsoft Research).

This month, we are highlighting three presentations from our August 2023 workshop on Large Language Models and Transformers. In this talk, OpenAI cofounder and chief scientist Ilya Sutskever presents a theory of unsupervised learning.

In July 2023, Nikhil Srivastava joined the Simons Institute as interim senior scientist. And with Shafi Goldwasser on sabbatical for the fall semester, Venkatesan Guruswami is serving as acting interim director through December 2023. The pair sat down last month to discuss their new roles, Nikhil’s research, and the intersections of math and TCS.