The Institute typically hosts two concurrent programs per semester. Programs are selected with a view toward maximizing impact and engagement across the theoretical computer science community, as well as impact on neighboring scientific fields. A typical one-semester program is led by a small group of organizers who are recognized experts in their fields, and involves about 60–70 long-term participants (a mix of senior and junior researchers) who spend a month or longer at the Institute. A program usually includes three week-long topical workshops, each of which attracts an additional group of invited speakers and focuses on a different aspect of the program's scientific scope, as well as an initial boot camp designed to put long-term participants on the same page.
This program studies the interaction between logic and the algorithms that they inspire, with applications to databases, complexity theory, and knowledge representation.
This program will bring together researchers in dynamic graphs, sketching, and optimization towards the common goals of obtaining provably faster algorithms, finding new connections between the areas, and making new advances at their intersection....
The Simons Institute for the Theory of Computing offers numerous ways for scientists to participate in the life of the Institute.
- Applications for the Simons Quantum Postdoctoral Fellowships.
- Applications for Science Communicators in Residence for Summer 2022, Fall 2022, and Spring 2023.
Classical approaches to algorithm design are both over-pessimistic (in making worst-case assumptions about the input) and over-optimistic (in assuming that the input is completely specified). This program explores alternatives to worst-case analysis of algorithms, as well as new methods for addressing uncertainty in instance specifications, with reference to a broad range of applications in learning, optimization and control.
Research on computational aspects of counting problems and partition functions has recently seen significant advances. This program aims to better understand the computational complexity of both exact and approximate counting problems, and their relationship to phase transitions in combinatorics and statistical physics.
Economics and computer science have developed a remarkable number of points of contact over the past two decades. This program aims to build on these existing interactions in order to identify and make progress on a new generation of research problems at the intersection of the two fields.
As organizations and individuals are increasingly outsourcing storage and computation to large third-party systems, the need to simultaneously guarantee privacy, availability of data and correctness of computations is more crucial than ever. This program focuses on new developments in cryptography that address these issues, including homomorphic encryption, program obfuscation and verifiable outsourcing.
The program will bring together experts in information theory and theoretical CS to explore the application of information theoretic techniques in complexity theory and combinatorics, the theory and applications of coding theory, and connections between information theory, machine learning and big data.
Quantum Hamiltonian complexity is an exciting area combining deep questions and techniques from both quantum complexity theory and condensed matter physics. This interdisciplinary program will explore these connections and seek to establish a common language for investigating the outstanding issues at the heart of quantum Hamiltonian complexity.
The objective of this program is to bring together theoretical computer scientists and researchers from evolutionary biology, physics, probability and statistics in order to identify and tackle the some of the most important theoretical and computational challenges arising from evolutionary biology.
The goal of this program is to bring together mathematicians and computer scientists to study influences, measures of complexity of discrete functions, functional inequalities, invariance principles, non-classical norms, representation theory and other modern topics in mathematical analysis and their applications to theoretical computer science.