Dear friends,

If you have visited the Simons Institute, you will be aware of the intensity of our research activity, and the creativity and productivity of our Research Fellows and long-term visitors. They gather for research discussions in our large, open interaction areas, and run an intensive schedule of seminars and reading groups that supplement the program workshops and Open Lectures. Their scientific interactions are enhanced by social interactions around shared interests, such as music, games, storytelling, cinema and hiking. As one measure of their productivity, in this year’s FOCS and STOC, the leading conferences in theoretical computer science, thirty of the papers resulted from research that took place at the Institute, including two Best Paper awards and one Best Student Paper award.

This Fall, the Institute launched a new pilot program offering stipends to support visitors whose children accompany them to Berkeley. This issue of the newsletter includes a feature about the new Family-Friendly Stipend Program, and profiles of some of the awardees.

The Research Vignette, “Mathematical Software Obfuscation,” by Amit Sahai, a participant in the Summer 2015 Cryptography program, describes a fundamental cryptographic process called Indistinguishability Obfuscation (iO), which compiles a computer program into a form that is unintelligible to third parties.  Sahai illustrates the kinds of cryptographic security that can be achieved using iO, and discusses the problem of extending iO to broader classes of computing platforms.

Each issue of the newsletter includes “From the Inside” features on each of our current programs. For this issue, we’re sharing video footage of conversations with the program organizers: Christos Papadimitriou’s interview of Russell Impagliazzo, an organizer of the Fine-Grained Complexity and Algorithm Design program, and my interview of Tim Roughgarden, an organizer of the Economics and Computation program.  Impagliazzo poses the hypothesis that a certain key combinatorial search problem cannot be solved by any method more efficient than brute-force search. He shows that a proof or disproof of the hypothesis would shed new light on the exact complexity of many problems, including some that are already known to be efficiently solvable. Roughgarden discusses the growing field of algorithmic game theory, which explores the design and analysis of economic mechanisms such as online auctions, enabled by the Internet and Worldwide Web, which involve interactions among many self-interested agents.

Finally, Luca Trevisan’s regular column, “Looking Ahead,” gives a brief preview of the Spring 2016 programs. The program on Algorithmic Challenges in Genomics will bring together experimental biologists and theoretical computer scientists to explore how the exponentially increasing body of DNA sequence data and other biological data can be brought to bear on the problem of understanding how genes and proteins regulate the operation of living cells, with special emphasis on improving diagnosis and developing personalized therapies for cancer. The program on Counting Complexity and Phase Transitions will explore the computational complexity of problems of counting combinatorial configurations such as matchings, colorings and independent sets, a subject with rich connections to statistical physics and mixing rates of stochastic processes.

We wish you the best for the holiday season, and hope to see many of you in the new year.

Best regards,
Dick Karp

Related Articles:

Institute launches Family-Friendly Stipend Program
From the Inside, Fall 2015
Research Vignette: Mathematical Software Obfuscation
Looking Ahead, Spring 2016: Genomics and Counting