 | This article needs additional citations for verification .(February 2018) |
| Formation | 2012 |
|---|---|
| Type | Theoretical computer science research institute |
| Location | |
Director | Shafi Goldwasser |
| Website | simons.berkeley.edu |
The Simons Institute for the Theory of Computing at the University of California, Berkeley is an institute for collaborative research in theoretical computer science. [1]
Established on July 1, 2012 with a grant of $60 million from the Simons Foundation, [2] the Institute is housed in Calvin Lab, a dedicated building on the Berkeley campus. The Simons Institute brings together the leading researchers in theoretical computer science and related fields, as well as the next generation of outstanding young scholars, to explore deep unsolved problems about the nature and limits of computation.
Richard M. Karp was Founding Director of the Institute, and fellow Turing Award winner Shafi Goldwasser took over as Director on January 1, 2018. [3] [4]
The Institute aims to promote fundamental research on the foundations of computer science, as well as to expand the horizons of the field by exploring other scientific disciplines through a computational lens. This second and distinctive goal is motivated by the fact that natural phenomena in many scientific fields (including mathematics, statistics, physics, astronomy, biology and economics), or the models those fields have developed for these phenomena, are intrinsically computational in nature—from chemical processes in living cells to the self-organizing behavior of complex systems of interacting particles, to mechanisms governing human evolution and the collective behavior of competing agents in an economy. The insights gained from such explorations often reflect back to the theory of computation, opening new directions and advancing our understanding of fundamental issues in complexity theory and algorithms.
The Institute's core activities revolve around a rotating sequence of programs; a program typically runs for one semester, and there will usually be two concurrent programs each semester. [5] Run by a small group of organizers, a program typically includes 60-70 long-term participants (a mix of senior and junior researchers), with additional short-term visitors attending workshops during the semester. Junior participants are supported by the Fellowships program.
Program topics are intended to span all areas of theoretical computer science, as well as its connections to other scientific disciplines; the Institute particularly aims to identify programs that can potentially lead to substantial advances in the field, rather than promoting "business as usual".
| Semester | Program | Organizers |
|---|---|---|
| Spring 2024 | Error-Correcting Codes: Theory and Practice [6] | Sivakanth Gopi, Venkatesan Guruswami, Henry Pfister, Mary Wootters, Gilles Zémor |
| Spring 2024 | Quantum Algorithms, Complexity, and Fault Tolerance [7] | Anurag Anshu, Nikolas Breuckmann, Patrick Hayden, Sandy Irani, Urmila Mahadev, Umesh Vazirani |
| Summer 2024 | Sublinear Algorithms [8] | Clément Canonne, Artur Czumaj, Piotr Indyk, Jelani Nelson, Noga Ron-Zewi, Ronitt Rubinfeld, Asaf Shapira |
| Summer 2024 | Summer Cluster: AI, Psychology, and Neuroscience [9] | Shiry Ginosar, Justine Casselll, Alison Gopnik, Phillip Isola, Christos Papadimitriou, Amanda Seed, Antonio Torralba, Doris Tsao, Shimon Ullman |
| Summer 2024 | Extended Reunion: Theoretical Foundations of Computer Systems [10] | Ruzica Piskac, Moshe Vardi |
Computer science is the study of computation, information, and automation. Computer science spans theoretical disciplines to applied disciplines. Though more often considered an academic discipline, computer science is closely related to computer programming.
Computational physics is the study and implementation of numerical analysis to solve problems in physics. Historically, computational physics was the first application of modern computers in science, and is now a subset of computational science. It is sometimes regarded as a subdiscipline of theoretical physics, but others consider it an intermediate branch between theoretical and experimental physics — an area of study which supplements both theory and experiment.
Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.
Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, formal language theory, the lambda calculus and type theory.
A computer scientist is a scholar who specializes in the academic study of computer science.
The University of California, Berkeley College of Engineering is the engineering school of the University of California, Berkeley, a public research university in Berkeley, California.
Shafrira Goldwasser is an Israeli-American computer scientist and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology; a professor of mathematical sciences at the Weizmann Institute of Science, Israel; the director of the Simons Institute for the Theory of Computing at the University of California, Berkeley; and co-founder and chief scientist of Duality Technologies.
Narendra Krishna Karmarkar is an Indian mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.
Computational science, also known as scientific computing, technical computing or scientific computation (SC), is a division of science that uses advanced computing capabilities to understand and solve complex physical problems. This includes
Silvio Micali is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand, a proof-of-stake blockchain cryptocurrency protocol. Micali's research at the MIT Computer Science and Artificial Intelligence Laboratory centers on cryptography and information security.
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.
László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.
Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massachusetts Institute of Technology.
The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathematical science and specialized knowledge. The term "applied mathematics" also describes the professional specialty in which mathematicians work on practical problems by formulating and studying mathematical models.
Oscar H. Ibarra is a Filipino-American theoretical computer scientist, prominent for work in automata theory, formal languages, design and analysis of algorithms and computational complexity theory. He was a Professor of the Department of Computer Science at the University of California-Santa Barbara until his retirement in 2011. Previously, he was on the faculties of UC Berkeley (1967-1969) and the University of Minnesota (1969-1990). He is currently a Distinguished Professor Emeritus at UCSB.
Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology.
Yael Tauman Kalai is a cryptographer and theoretical computer scientist who works as a Senior Principal Researcher at Microsoft Research New England and as an adjunct professor at MIT in the Computer Science and Artificial Intelligence Lab.