ACM Symposium on Theory of Computing

ACM Symposium on Theory of Computing
Name	ACM Symposium on Theory of Computing
Abbreviation	STOC
Discipline	Theoretical Computer Science
Publisher	Association for Computing Machinery
Country	International
First	1969
Frequency	Annual

ACM Symposium on Theory of Computing The ACM Symposium on Theory of Computing is an annual scholarly conference central to Algorithms research, Computational complexity theory, Cryptography research, Distributed computing, and Quantum computing. It convenes researchers from institutions such as Massachusetts Institute of Technology, Stanford University, University of California, Berkeley, Princeton University, and University of Cambridge alongside participants from Microsoft Research, IBM Research, Google Research, Amazon, and Bell Labs. The meeting influences directions pursued at venues like International Colloquium on Automata, Languages and Programming, IEEE Symposium on Foundations of Computer Science, Conference on Learning Theory, Symposium on Principles of Database Systems, and IEEE FOCS.

History

STOC originated amid growth in Computer science research in the late 1960s, following initiatives at Association for Computing Machinery, RAND Corporation, Bell Labs Research, Carnegie Mellon University, and University of Illinois at Urbana–Champaign. Early attendees included researchers from Harvard University, Yale University, Columbia University, Cornell University, Brown University, University of Toronto, Australian National University, and École Normale Supérieure. Over decades STOC has intersected with milestones associated with figures from Donald Knuth, Richard Karp, John Hopcroft, Leslie Valiant, Shafi Goldwasser, Silvio Micali, Peter Shor, Lovász László, Sanjeev Arora, and Avi Wigderson. The Symposium adapted formats influenced by parallel events like NeurIPS, International Symposium on Information Theory, SIGMOD, and SODA.

Scope and Topics

STOC covers themes spanning Computational complexity theory, Approximation algorithms, Randomized algorithms, Communication complexity, Quantum complexity theory, Cryptography research, Data structures research, Streaming algorithms, Property testing, Computational geometry, and Game theory. Subareas frequently represented include work by authors affiliated with ETH Zurich, École Polytechnique, University of Oxford, Weizmann Institute of Science, University of Washington, University of Chicago, Tel Aviv University, Montréal Institute for Learning Algorithms, and Centre for Quantum Technologies. Cross-disciplinary dialogues often involve collaborators from National Institute of Standards and Technology, Institute for Advanced Study, Simons Institute for the Theory of Computing, and Perimeter Institute.

Conference Organization and Sponsorship

The Symposium is organized under the auspices of Association for Computing Machinery and its Special Interest Group SIGACT; program committees draw members from SIGPLAN, SIGGRAPH, IEEE Computer Society, Royal Society, National Science Foundation, and institutional partners such as Microsoft Research and Google Research. Conference chairs and program chairs have historically been drawn from Stanford University, Princeton University, MIT, UC Berkeley, Columbia University, Harvard University, Carnegie Mellon University, University of Toronto, ETH Zurich, and École Polytechnique Fédérale de Lausanne. Sponsorship and grants have come from entities including NSF, DARPA, Simons Foundation, Google, Microsoft, IBM, Amazon Web Services, and philanthropic organizations such as Alfred P. Sloan Foundation.

Proceedings and Publication

Accepted papers are published in proceedings overseen by the Association for Computing Machinery and archived in the ACM Digital Library, appearing alongside proceedings from IEEE FOCS, ICALP, ESA (conference), and ICALP. Authors often also present extended versions in journals such as Journal of the ACM, SIAM Journal on Computing, Communications of the ACM, and IEEE Transactions on Information Theory. Selected STOC talks have been expanded into monographs and textbooks from presses including MIT Press, Cambridge University Press, Springer, and Oxford University Press.

Notable Results and Influential Papers

STOC has been the venue for landmark results such as work on NP-completeness and reducibility influenced by Richard Karp, advances in Probabilistically Checkable Proofs related to researchers at Bell Labs and Princeton University, breakthroughs in Interactive proof systems tied to Shafi Goldwasser and Silvio Micali, and foundational quantum algorithms connected to Peter Shor and Lovász László. Other influential contributions include results on expander graphs by researchers associated with Princeton University and University of Chicago, developments in property testing from teams at MIT and Weizmann Institute of Science, and progress on sublinear algorithms and streaming algorithms by groups at IBM Research and University of California, San Diego. Many papers have catalyzed work later cited in landmark projects at Google DeepMind, Microsoft Research Redmond, Simons Institute, and national labs such as Argonne National Laboratory.

Awards and Recognition

STOC presentations and authors have received major awards including the Turing Award, Gödel Prize, Nevalinna Prize, Polya Prize, MacArthur Fellowship, and fellowships from Royal Society and National Academy of Sciences. Best paper awards and recognition often align with honors from SIAM, IEEE, European Research Council, Royal Society, and American Mathematical Society. Program committee members and keynote speakers have included recipients of ACM Prize in Computing, Knuth Prize, IEEE John von Neumann Medal, and various national science medals.

Attendance and Community Impact

The Symposium attracts attendees from leading universities such as University of California, Los Angeles, Imperial College London, University of Michigan, University of Pennsylvania, Johns Hopkins University, Duke University, Brown University, Rutgers University, and industrial labs including Facebook AI Research, Apple, and IBM Research. STOC fosters collaborations that lead to research clusters at Simons Institute for the Theory of Computing, Microsoft Research Cambridge, Google Research New York, Perimeter Institute, and advisory roles in policymaking bodies like National Science Foundation panels and international consortia. Its community activities include workshops, doctoral consortia, and mentoring programs connected to organizations such as CRA (Computing Research Association) and SIGACT.

Category:Theoretical computer science conferences