Letter from the Director, June 2018

Shafi Goldwasser photo

Dear friends,

This is my first letter to you as the Director of the Simons Institute. I am honored to be replacing Dick Karp, who has made the Simons Institute a resounding success, and I feel very lucky to be joining my partners in leadership, Associate Director Peter Bartlett and Senior Scientist Luca Trevisan. Thank you, Peter and Luca, for your warm welcome and friendship.

Joining the Institute is especially meaningful for me, as it signifies coming back to a place that marked the beginning of my scientific career and holds many dear memories, both scientific and personal. Berkeley in the '80s was a hotbed of creativity, with the inventions of pseudorandomness, average-case analysis of algorithms, randomized methods of encryption, extractors and semi-random sources, to mention a few. I believe we are in a similarly exciting time today in the evolution of the field of computer science. The importance of establishing sound theoretical foundations in the fields of data science and privacy is paramount today. The Simons Institute can and should play a central role in developing the necessary definitions, models, and mathematical treatment.

During Spring 2018, the Institute ran two exciting programs.

The Program on The Brain and Computation brought together neuroscientists and computer scientists to investigate how the brain represents and stores information, how it "computes," and how feedback processes (in which a stimulus provides a reaction) work. The program came at a time of increasing availability of data about the brain, and a corresponding need for mathematical models to interpret the data. The three workshops were on (1) how the brain represents data and computes, (2) how to work with the increasing amount of data about brain structure and dynamics, and (3) computational models of the brain.

The program on Real-Time Decision Making focused on algorithmic techniques for application domains in which data is generated continuously and one wants to make decisions (1) quickly, and (2) without full knowledge of future data. Examples include how to manage electrical grids, how to manage ride-sharing services, how to manage a public transportation network, and how to deal with the data generated by particle accelerators and astronomical observatories. There was a workshop on natural sciences applications (e.g. accelerators and observatories); two workshops on societal networks – not meaning Facebook and Twitter, but things like the power grid or a public transit network; and a workshop on algorithms.

In our From the Inside series, we offer articles on the Spring 2018 programs.

Laurenz Wiskott's article on the program on The Brain and Computation sheds light on the strongly interdisciplinary nature of the program, which brought together neuroscientists and computer scientists from all over the world to exchange ideas.

Richard Karp's article on the Real-Time Decision Making program highlights the program's three workshops, which focused on real-time discovery and inference in the natural sciences and physical systems, and societal networks; and mathematical and computational challenges in real-time decision making. In particular, the first workshop resulted in launching a new line of research on allocating telescope resources to maximize the probability of detecting supernovae and other astronomical phenomena. The second workshop emphasized the use of machine learning, control theory, game theory, market design, pricing, and incentives in the management of urban systems. A major theme of the third workshop was the design of algorithms for traffic control with the availability of partial and imperfect information.

Brian Hayes, our Journalist in Residence, has written a feature article on the program on The Brain and Computation. His conclusion, from spending five months surrounded by neuroscientists and computer scientists looking for a common language, is that their differences in scientific traditions are at least as important as the similarities. Whereas the neuroscientists appreciate the intricate complexity of the brain's fabric, the computer scientists aspire to replace this detail with as-simple-as-possible mathematical abstractions.

This issue of the newsletter includes a wonderful Research Vignette by James Lee on online optimization, where algorithms must take actions in the face of uncertainty about the future, discussed in the wake of the rise of machine learning. He recalls two algorithmic paradigms: competitive analysis of algorithms, which has been studied in theoretical CS since the 1970s; and multi-arm bandits, which arises in online learning where the goal of an algorithm is to achieve a total cost that is not too much worse than the best fixed action in hindsight. Lee shows how the models are quite similar. He then describes how a collaboration seeded at the Simons Institute, and spanning three years (and two separate programs), was key in developing a theory strong enough to attack the k-server problem, transferring ideas from the theory of multi-arm bandits to competitive analysis.

Luca Trevisan's regular column, "Looking Ahead," describes our upcoming programs. This summer, the Simons Institute is hosting activities on Quantum Computing and on Algorithmic Fairness; and in the coming fall, we will host programs on Data Science and on Lower Bounds.

The Summer Cluster on Challenges in Quantum Computation is the Simons Institute's first experiment with a shorter-length program format. The cluster will run for eight weeks during the summer, with about 30 visitors coming to Berkeley, and run a single one week-long workshop. A smaller cluster on Algorithmic Fairness will run in the later part of the summer. The fall program on Foundations of Data Science is part of the Simons Institute's long-term focus on building theoretical foundations for data science. And the program on Lower Bounds in Computational Complexity will focus on unconditional impossibility results in various computational models, including communication complexity, boolean circuits, algebraic circuits, branching programs, and proof systems.

I look forward to seeing you in Berkeley soon.

All best,
Shafi 

Shafi Goldwasser
Director, Simons Institute for the Theory of Computing

Related Articles

Related stories

,