Letter from the Director, Fall 2016

Dear friends,

The research programs of the Simons Institute during the year 2016, as well as those planned for Spring 2017, explore novel directions in the study of algorithms, and reach out to several disciplines, including molecular biology, statistical physics, quantum mechanics, artificial intelligence, and several areas within mathematical logic and pure mathematics. This issue of the newsletter features essays on all these topics, and also provides a glimpse at how our visiting scientists enjoy and benefit from their time at the Institute.

Teresa Przytycka and Roded Sharan, in their Research Vignette on work that took place during the Spring 2016 program on Algorithmic Challenges in Genomics, describe methods to analyze the progression of cancer in terms of disease modules, sets of functionally related genes in which driver mutations provide a growth advantage to evolving tumor cells.

Nike Sun and Allan Sly, members of the Spring 2016 program on Counting Complexity and Phase Transitions, present a Research Vignette on phase transitions – sudden changes in the character of a random constrained mathematical or physical system at a critical value of a parameter. For example, in the k-satisfiability problem of propositional logic, one is given m random constraints, each involving k Boolean variables out of a set of n variables. It is believed that, at a certain critical ratio of the number of constraints to the number of variables, the system of constraints flips from almost certainly satisfiable to almost certainly unsatisfiable. The most promising approaches to understanding phase transitions in random constraint satisfaction problems in computer science stem from the work of statistical physicists, who have successfully analyzed phase transitions in spin glasses, which model the behavior of certain magnetic alloys.

Avrim Blum, an organizer of the Fall 2016 program on Algorithms and Uncertainty, in his From the Inside article on the program, describes methods of exploiting special structure in the input data for an algorithm, or adapting to information or constraints that are not known in advance, but become known in the course of executing an algorithm. These extensions often complement the traditional worst-case analysis of an algorithm to give a more realistic view of its capabilities.

Val Tannen’s From the Inside article on the concurrent program this fall on Logic and Computation describes the two main themes underlying the program: the interaction of logic with the analysis of algorithms and computational complexity, and the study of the semantics of programs and processes. The program focuses on the interplay between logic and probability and between logic and quantum mechanics, as well as on finite model theory, in which the meaning of logical sentences is restricted to finite (or finitely definable) structures. Finite model theory provides a foundation for the theory of database systems and sheds light on computational complexity theory.

In his regular column, Looking Ahead, Simons Institute Senior Scientist Luca Trevisan introduces our Spring 2017 programs on Pseudorandomness and Machine Learning. The Machine Learning program explores algorithms for interactive learning, in which a concept is imparted through a dialogue between a teacher and a learner, and representation learning, in which the goal is to discover the features of data that are salient for particular pattern recognition or classification tasks. The theory of Pseudorandomness deals with the deterministic construction of mathematical objects, such as bit strings or graphs, that are computationally indistinguishable from purely random objects. The theory has close ties to analytic number theory and additive combinatorics, and has bearing on cryptography and on the derandomization of randomized algorithms.

This fall, the Institute welcomed Erica Klarreich as our inaugural Journalist in Residence. You can read an interview with Erica in this issue of the newsletter, and learn more about our new residency program. The newsletter also features an article by Erica, profiling four of the current Research Fellows at the Institute. All of them were highly enthusiastic about their experience. They described it as intense and invigorating, and praised the quality of their fellow scientists and the opportunities for collaboration. In the words of Marco Molinaro, it is an environment that no conference or visiting position in a computer science department can match.

Best regards,
 
Dick Karp
Director

Related Articles

• “All sorts of surprising connections”: Conversations with Research Fellows Marco Molinaro, Joanna Ochremiak, Matt Weinberg and Christoph Berkholz
• Simons Institute Launches Journalist-in-Residence Program
• From the Inside: Logical Structures in Computation
• From the Inside: Algorithms and Uncertainty
• Research Vignette: Network Biology Meets Cancer Genomics
• Research Vignette: Phase Transitions in Random Constraint Satisfaction Problems
• Looking Ahead: Machine Learning and Pseudorandomness