Symposium on Theory of Computing

The Symposium on Theory of Computing (STOC) is an annual conference organized by the Association for Computing Machinery (ACM) that focuses on the field of theoretical computer science. Lauded as one of the premier conferences in the field, STOC provides a platform where the most innovative and groundbreaking work in theoretical computing is presented and discussed.

Importance and Scope

STOC, along with its counterpart, the Symposium on Foundations of Computer Science (FOCS), is considered instrumental in defining the landscape of theoretical computer science. These conferences bring together researchers from across the globe to present papers that explore new ideas, solve open problems, and broaden the scope of the field. The work presented often includes significant advancements in areas like cryptography, computational learning theory, graph theory, and many others.

Key Features

• Broad Reach: Contributions are not confined to a single aspect of computer science but rather span various domains to foster interdisciplinary research and collaboration.

• Papers and Presentations: STOC solicits papers that not only address existing problems but also propose new and potentially impactful questions. Topics may range from lattice-based cryptography to the graph isomorphism problem.

• Awards and Recognition: The conference awards prizes for outstanding papers, including those authored by students, encouraging young researchers to contribute to the field. The prestigious Gödel Prize is often associated with STOC, awarded for outstanding papers in theoretical computer science.

• SIGACT Business Meeting: Held during the conference, this meeting is open to all members of the theoretical computer science community. It is an opportunity for attendees to engage with the broader organizational aspects of the field.

Historical Contributions

STOC has been the venue for the presentation of many seminal papers in theoretical computer science. Landmark contributions include discussions on the complexity of theorem-proving procedures and the introduction of limitations on learning boolean formulae in computational learning theory. These works have laid the groundwork for further research and development in their respective areas.

Community and Collaboration

STOC is known for fostering a strong sense of community among theoretical computer scientists. As Fich notes, regular attendance at STOC and FOCS is seen as a defining characteristic of a theoretical computer scientist. The collaborative environment of the conference allows researchers to stay abreast of developments across the entire field and engage with thought leaders who are pushing the boundaries of what is possible through computing.

Related Topics

• Lattice Problem
• Verifiable Computing
• Association for Computing Machinery
• Complexity Theory

The Symposium on Theory of Computing continues to be a cornerstone of theoretical computer science, facilitating the dissemination of knowledge and fostering the exploration of new and challenging problems.