Dear friends,

Composing this letter will be my last official act as Director of the Simons Institute, as I am about to step down after a five-year term. Under the leadership of our new Director, Shafi Goldwasser, Associate Director Peter Bartlett, and Senior Scientist Luca Trevisan, the Institute will continue to bring together interdisciplinary groups of leading scientists in focused research programs that explore the foundations of computation and its role in science and society. The articles in this newsletter illustrate the depth and broad scope of the Institute’s activities.

During Fall 2017, the full resources of the Institute were devoted to an extra-large program on Bridging Discrete and Continuous Optimization. In our From the Inside series, we offer two articles on the program.

Daniel Dadush’s article describes the disparate histories of these two branches of optimization and recent breakthroughs that have led to more efficient ways of combining the discrete and continuous approaches to solve large-scale optimization problems. The program pursued connections between optimization and wider mathematical areas, from machine learning to high-dimensional geometry and real algebraic geometry. The workshops in the program explored the use of continuous relaxations to solve discrete problems, fast iterative methods in continuous optimization, the power and limitations of linear and semi-definite programs for approximating constraint satisfaction problems, and key challenges from machine learning and statistics.

Ben Recht’s article describes a symposium at the Institute exploring Model Predictive Control (MPC), an important paradigm for robot planning and actuation in which a robot repeatedly makes a plan based on a simulation from the present until a short time into the future, and then executes one step of the plan. Russ Tedrake discussed challenges for MPC in robotic control through physical contacts. Francesco Borrelli discussed MPC in the context of autonomous driving, and Anca Dragan presented an optimization paradigm for robotic planning when humans are in the loop, leading to the issues of inferring the objectives being pursued by human agents.

Rapid progress in deep learning has led to great success in teaching machines to recognize familiar objects in images with precision approaching or exceeding human vision. Sanjeev Arora’s Research Vignette, “Promise and limitations of Generative Adversarial Nets (GANs),” on research conducted in the Spring 2017 program on Foundations of Machine Learning, goes beyond recognition tasks to the more creative task of generating plausible examples of landscapes and scenes. He discusses a technique for learning a generative model by playing an iterative game between the generator and a discriminator that attempts to distinguish between real examples and the synthetic outputs of the generator.

The Research Vignette by Amnon Ta Sh'ma entitled "Ramsey Graphs and the error of explicit 2-source extractors" describes a result by Eshan Chattopadhyay and David Zuckerman that was a focus of attention in the Spring 2017 program on Pseudorandomess. Informally, the result states that, given two weak sources of random bits, one can efficiently output a string that is statistically indistinguishable from uniform. This result implies an improvement on a famous combinatorial question in graph theory: given N, what is the smallest value of K for which we can explicitly construct a graph on N vertices such that every set of size K is neither a clique nor an independent set? The same result in Ramsey theory was also obtained by a different approach by Gil Cohen, also a participant in the Pseudorandmness program.

In his article, “In Order Not to Discriminate, We Might Have to Discriminate,” Christoph Drösser, the Fall 2017 Journalist in Residence at the Simons Institute, reports on a recent symposium at the Simons Institute discussing issues of fairness and discrimination arising when algorithms supplant humans in tasks such as deciding who gets a loan, a job, or parole from prison. While the conventional wisdom is that fairness is achieved best when the algorithm is blind to “protected categories” such as sex, race, religion or age, the omission of those categories can sometimes actually worsen discrimination.

Luca Trevisan’s regular column, Looking Ahead, gives a preview of the two highly interdisciplinary programs upcoming in Spring 2018. The program on The Brain and Computation will explore knowledge representation and computation in the brain, applications of brain science to computer science, and the analysis of the large amount of data about brain function and anatomy that has recently become available. The program on Real-Time Decision Making is motivated by applications in science and engineering where a large amount of observational data is continuously generated and important decisions based on that data have to be made in real time. A wide variety of tools from computer science, machine learning, statistics and control theory will be brought to bear on applications from robotic astronomy, earthquake early warning, urban transportation and control of the energy grid.

Russell Impagliazzo sat down with me in the final semester of my term as Director to talk about some of the developments in the field of Theoretical Computer Science over the course of my career. We’re pleased to share the video of that interview with you.

In September 2017, the Institute and the Theoretical Computer Science community lost one of its rising stars. Michael Cohen was brilliant researcher, and a Fellow in the Optimization program when he died unexpectedly, of natural causes. Some of his close friends and collaborators have written an In memoriam piece in his honor, which appears in this issue of the newsletter.

It has been an honor to serve the Theoretical Computer Science community as Founding Director of the Simons Institute. I will be at the Institute this spring as an organizer of the program on Real-Time Decision Making, and look forward to seeing many of you in Calvin Lab and enjoying life on the other side.

All best wishes,
Dick Karp
Director, Simons Institute

Related Articles

• In Memoriam: Michael B. Cohen (1992 - 2017)
• In Order Not to Discriminate, We Might Have to Discriminate
• From the Inside: Optimization (1 of 2)
• From the Inside: Optimization (2 of 2)
• Research Vignette: Ramsey Graphs and the Error of Explicit 2-Source Extractors
• Research Vignette: Promise and Limitations of Generative Adversarial Nets (GANs)
• Oral History: Russell Impagliazzo in Conversation with Dick Karp
• Simons Institute YouTube Channel Reaches 1 Million Views
• Looking Ahead: Spring 2018