Symposium on Foundations of Computer Science

Last updated

The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society.

Contents

As Fich (1996) writes, FOCS and its annual Association for Computing Machinery counterpart STOC (the Symposium on Theory of Computing) are considered the two top conferences in theoretical computer science, considered broadly: they “are forums for some of the best work throughout theory of computing that promote breadth among theory of computing researchers and help to keep the community together.” Johnson (1984) includes regular attendance at FOCS and STOC as one of several defining characteristics of theoretical computer scientists.

Awards

The Knuth Prize for outstanding contributions to theoretical computer science is presented alternately at FOCS and STOC. Works of the highest quality presented at the conference are awarded the Best Paper Award. [1] In addition, the Machtey Award is presented to the best student-authored paper in FOCS.

History

In 1960–1965, FOCS was known as the Symposium on Switching Circuit Theory and Logical Design, and in 1966–1974 it was known as the Symposium on Switching and Automata Theory. The current name has been used since 1975. Since 1973, the cover page of the conference proceedings has featured an artwork entitled synapse, by Alvy Ray Smith, who has also been the author of three papers in the conference. [2] The publisher uses the acronym SFCS on their web sites for the conferences in 1975 to 1987. [3]

Location

FOCS is almost exclusively held in North America, and in particular in the United States, with few exceptions. [4]

YearPC and Local ChairsLocationSteering CommitteeTest of Time Award Committee
1975 Daniel Rosenkrantz (PC Chair), Eugene Lawler (Local Chair)Berkeley
1976 Michael Fischer (PC Chair), Meera Blattner (Local Chair)Houston
1977 Paul Young (PC Chair), John Savage (Local Chair)Providence
1978 Nancy Lynch (PC Chair), William Rounds (Local Chair)Ann Arbor
1979 Rao Kosaraju (PC Chair), Rolando Peinado (Local Chair)San Juan, Puerto Rico
1980Syracuse
1981 Arnold Rosenberg (PC Chair), Patrick Fischer (Local Chair)Nashville
1982Chicago
1983 Lawrence Snyder (PC Chair), Peter Downey (Local Chair)Tucson
1984Singer Island
1985 Robert Tarjan (PC Chair), Eugene Luks (Local Chair)Portland
1986 John Hopcroft (PC Chair), Charles Rackoff (Local Chair)Toronto Ashok Chandra (TCMF Chair)
1987 Tom Leighton (PC Chair), Seymour Ginsburg (Local Chair), Ming-Deh Huang (Local Chair)Los Angeles"
1988White Plains
1989 Zvi Galil (PC Chair), Jon Reif (Local Chair)Research Triangle Park Christos Papadimitriou (TCMF Chair)
1990 Mihalis Yannakakis (PC Chair), Jonathan Turner (Local Chair)St. Louis"
1991 Mike Sipser (PC Chair), Tom Leighton (Local Chair), Alok Aggarwal (Local Chair)San Juan, Puerto Rico"
1992 Michael Luby (PC Chair), Gary Miller (Local Chair)Pittsburgh
1993 Leonidas J. Guibas (PC Chair), Andrei Broder (Local Chair)Palo Alto
1994 Shafi Goldwasser (PC Chair), Sorin Istrail (Local Chair)Santa Fe
1995 Prabhakar Raghavan (PC Chair), Aditi Dhagat (Local Chair), Rene Peralta (Local Chair)Milwaukee
1996 Martin Tompa (PC Chair), Carl Smith (Local Chair)Burlington
1997 Anna Karlin (PC Chair), Victor Milenkovic (Local Chair)Miami Beach
1998 Rajeev Motwani, Michael Mitzenmacher (Local Chair)Palo Alto
1999 Paul Beame (PC Chair), Piotr Berman (Local Chair)New York
2000 Avrim Blum (PC Chair), Marek Chrobak (Local Chair), Tao Jiang (Local Chair)Redondo Beach
2001 Moni Naor (PC Chair), Lawrence Larmore (Local Chair), Wolfgang Bein Las Vegas
2002 Bernard Chazelle (PC Chair) Arvind Gupta (Local Chair)Vancouver, Canada
2003 Madhu Sudan (PC Chair), Michael Mitzenmacher (Local Chair)Cambridge
2004 Eli Upfal(PC Chair), Giuseppe F. Italiano (Local Chair)Rome, Italy
2005 Eva Tardos (PC Chair), Avrim Blum (Local Chair), Anupam Gupta (Local Chair)Pittsburgh
2006 Sanjeev Arora, Satish Rao (Local Chair)Berkeley
2007 Alistair Sinclair (PC Chair), Philip Klein (Local Chair), Anna Lysyanskaya (Local Chair), Claire Mathieu (Local Chair)Providence
2008 R. Ravi (PC Chair), Sudipto Guha (Local Chair), Sanjeev Khanna (Local Chair), Sampath Kannan (Local Chair)Philadelphia Paul Beame (TCMF Chair)
2009 Dan Spielman (PC Chair), David Shmoys (General co-Chair), Milena Mihail (Local Chair), Prasad Tetali (Local Chair)Atlanta"
2010 Luca Trevisan (PC Chair), Larry Larmore (Local Chair)Las Vegas"
2011 Rafail Ostrovsky (PC Chair), Marek Chrobak (Local Chair), Neal Yong (Local Chair),Palm Springs"
2012 Tim Roughgarden (PC Chair), Rebecca Wright (Local Chair), Lisa Zhang (Local Chair), Boaz Barak (Workshop Chair), Avrim Blum (Workshop Chair)New Brunswick David Shmoys (TCMF Chair)
2013 Omer Reingold (PC Chair), Christos Papadimitriou (Local Chair), Umesh Vazirani (Local Chair), Moses Charikar (Workshop Chair), Chris Umans (Workshop Chair)Berkeley"
2014 Boaz Barak (PC Chair), Rebecca Wright (Local Chair), Lisa Zhang (Local Chair), Sanjeev Khanna (Workshop Chair), Kunal Talwar (Workshop Chair)Philadelphia"
2015 Venkatesan Guruswami (PC Chair), Kristin Kane (Local Chair), Prasad Raghavendra, Luca Trevisan Berkeley Rafail Ostrovsky (TCMF Chair)
2016 Irit Dinur (PC Chair), Rebecca Wright (Local Chair), Lisa Zhang (Local Chair), Alexandr Andoni (Workshop Chair), Aleksander Mądry (Workshop Chair)New Brunswick"
2017 Chris Umans (PC Chair), Andrew Jan (Local Chair), Prasad Raghavendra (Local Chair), Aleksander Mądry (Workshop Chair), James R. Lee (Workshop Chair)Berkeley"
2018 Mikkel Thorup (PC Chair), Adi Rosén (Local Chair), Sophie Laplante (Local co-Chair), Alessandro Luongo (Local co-Chair), Robert Kleinberg (Workshop Chair), James R. Lee (Workshop Chair)Paris, France Yuval Rabani (TCMF Chair), Shang-Hua Teng (TCMF Vice Chair), Avrim Blum, Shafi Goldwasser, Rafail Ostrovsky, Toniann Pitassi
2019 David Zuckerman (PC Chair), Michael Dinitz (Local Chair), Maria-Florina Balcan (Workshop Chair), Robert Kleinberg (Workshop Chair)Baltimore" Paul Beame, Allan Borodin, Uriel Feige, Monika Henzinger, Johan Håstad (chair), Mihalis Yannakakis (inaugural award)
2020 Sandy Irani (PC Chair), Debmalya Panigrahi (Local Chair), Kamesh Munagala (Local Chair), Maria-Florina Balcan (Workshop Chair), Alexander Sherstov (Workshop Chair)Virtual (planned for Raleigh/Durham)" Paul Beame (chair), Uriel Feige, Anna Karlin, Yishay Mansour, Claire Mathieu, Luca Trevisan
2021 Nisheeth Vishnoi (PC Chair), Alexandra Kolla (Local/Finance Chair), Vincent Cohen-Addad (Workshop Chair), Alexander Sherstov (Workshop Chair)Virtual (planned for Denver)" Russell Impagliazzo, Yael Tauman Kalai, Anna Karlin, Yishay Mansour, Michael Saks, Luca Trevisan (chair)
2022 Jelani Nelson (PC chair), Alexandra Kolla (Local Chair), Rong Ge (Finance Chair), Vincent Cohen-Addad (Workshop Chair), Henry Yuen (Workshop Chair)Denver Shang-Hua Teng (TCMF Chair), Venkatesan Guruswami (TCMF Vice Chair), Avrim Blum, Shafi Goldwasser, Rafail Ostrovsky, Toniann Pitassi, Yuval Rabani Russell Impagliazzo, Yael Tauman Kalai, Michael Saks (chair), Alistair Sinclair, Éva Tardos, David Zuckerman
2023 Amit Sahai (PC Chair), Shubhangi Saraf (PC Co-chair), Thomas Vidick (PC Co-chair), Alexandra Kolla (General Chair), Pravesh Kothari (Workshop Chair), Henry Yuen (Workshop Chair)Santa Cruz" Jin-Yi Cai, Faith Ellen, Leonard Schulman, Alistair Sinclair, Éva Tardos, David Zuckerman (chair)
2024 Santosh Vempala (PC Chair), Aravindan Vijayaraghavan (General Chair), Lev Reyzin (General Chair), Mohsen Ghaffari (Workshop Chair), Pravesh Kothari (Workshop Chair)Chicago Ran Canetti (TCMF Chair), Rocco Servedio (TCMF Vice Chair)

See also

Related Research Articles

The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM).

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

<span class="mw-page-title-main">Russell Impagliazzo</span> American computer scientist

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.

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.

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

The Machtey Award is awarded at the annual IEEE Symposium on Foundations of Computer Science (FOCS) to the author(s) of the best student paper(s). A paper qualifies as a student paper if all authors are full-time students at the date of the submission. The award decision is made by the Program Committee.

Frances Foong Chu Yao is a Taiwanese-American mathematician and theoretical computer scientist. She is currently a Chair Professor at the Institute for Interdisciplinary Information Sciences (IIIS) of Tsinghua University. She was Chair Professor and Head of the Department of computer science at the City University of Hong Kong, where she is now an honorary professor.

The ACM Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery.

Larry Joseph Stockmeyer was an American computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing. He died of pancreatic cancer.

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.

<span class="mw-page-title-main">Ran Raz</span>

Ran Raz is a computer scientist who works in the area of computational complexity theory. He was a professor in the faculty of mathematics and computer science at the Weizmann Institute. He is now a professor of computer science at Princeton University.

Ashok K. Chandra was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center. Chandra received his PhD in Computer Science from Stanford University, an MS from University of California, Berkeley, and a BTech from IIT Kanpur. He was previously Director of Database and Distributed Systems at IBM Almaden Research Center.

Amos Fiat is an Israeli computer scientist, a professor of computer science at Tel Aviv University. He is known for his work in cryptography, online algorithms, and algorithmic game theory.

Christopher Umans is a professor of Computer Science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, computational complexity, algebraic complexity, and hardness of approximation.

Ronald Michiel de Wolf is a Dutch Computer Scientist, currently a Senior Researcher at Centrum Wiskunde & Informatica (CWI) and a professor at the Institute for Logic, Language and Computation (ILLC) of the University of Amsterdam (UvA).

Michael A. Bender is an American computer scientist, known for his work in cache-oblivious algorithms, lowest common ancestor data structures, scheduling (computing), and pebble games. He is David R. Smith Leading Scholar professor of computer science at Stony Brook University, and a co-founder of storage technology startup company Tokutek.

<span class="mw-page-title-main">Philip N. Klein</span> American computer scientist

Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs. 

References

Notes

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.