← Back to home

Symposium On Theory Of Computing

Alright, let's dissect this. You want me to take something… dry… and imbue it with a semblance of life. Or at least, make it less like a dusty relic unearthed from a forgotten archive. Fine. But don't expect sunshine and rainbows. This is theoretical computer science, after all. It’s meant to be sharp, precise, and occasionally, a little bit… unpleasant. Much like certain conversations I’ve had.

The Annual ACM Symposium on Theory of Computing (STOC)

An Arena for the Sharpest Minds in Theoretical Computer Science

The Annual ACM Symposium on Theory of Computing, or STOC as it's known in circles that appreciate brevity (and I do), is no casual gathering. It's a crucible, a battleground for ideas in theoretical computer science. Since 1969, usually emerging from the shadows in May or June, STOC has been the annual proving ground. It’s orchestrated by the Association for Computing Machinery, specifically its special interest group, SIGACT. Think of it as the intellectual heavyweight championship, where algorithms are the contenders and proofs are the knockout blows.

The acceptance rate? A mere 31% on average from 1970 to 2012. In 2012, it dipped to a rather unforgiving 29%. [1] This isn't a place for the faint of heart, or those who believe in participation trophies. It’s where the truly exceptional are sifted from the… well, from the rest.

As Faith Fich so eloquently put it in 1996, STOC, alongside its annual IEEE counterpart, the Symposium on Foundations of Computer Science (FOCS), stands as the undisputed pinnacle of theoretical computer science. [2] They are not just conferences; they are vital arteries, pumping the lifeblood of innovation through the community, ensuring a breadth of research and, crucially, keeping the fragmented minds of theorists tethered together. David S. Johnson, back in 1984, even posited that regular attendance at STOC and FOCS was a defining characteristic of a theoretical computer scientist. [3] Imagine that. So, if you’re found lurking in the halls of STOC, you’re already marked.

The Accolades: More Than Just a Pat on the Back

The Gödel Prize, awarded for groundbreaking papers in theoretical computer science, makes its appearance at STOC or its European counterpart, the International Colloquium on Automata, Languages and Programming (ICALP), alternatingly. It’s a testament to work that truly shifts paradigms. Then there’s the Knuth Prize, a recognition of profound contributions to the foundations of computer science, which also graces STOC and FOCS in turn. These aren’t trinkets; they are markers of intellectual conquest.

Since 2003, STOC has seen fit to bestow Best Paper Awards [3] upon those works that rise above the rest, shining with an almost offensive brilliance. But it doesn’t stop there. The Danny Lewin Best Student Paper Award is reserved for the best work authored solely by students. It’s named in honor of Daniel M. Lewin, a brilliant mathematician and entrepreneur, a co-founder of Akamai Technologies, whose life was tragically cut short in the September 11 attacks. [4] [5] A somber reminder that even in the sterile realm of theory, real lives, and real losses, cast long shadows.

A Chronicle of Significance: The Genesis of STOC

The first STOC convened on May 5–7, 1969, in the rather unassuming locale of Marina del Rey, California, United States. The chairman, Patrick C. Fischer, presided over a program committee that reads like a who's who of the field's pioneers: Michael A. Harrison, Robert W. Floyd, Juris Hartmanis, Richard M. Karp, Albert R. Meyer, and Jeffrey D. Ullman. [6] A formidable assembly.

Among the foundational papers that first saw the light of day at STOC is Stephen Cook's 1971 work, which introduced the earth-shattering concept of NP-completeness. [7] Yes, that Cook. The one whose insights, along with the Cook–Levin theorem, laid the groundwork for so much of what we now grapple with.

The Itinerant Nature of Genius: Where STOC Lands

STOC has, at times, ventured beyond its usual American haunts. It’s been hosted in Canada in 1992, 1994, 2002, 2008, and 2017. Greece played host in 2001. Then, the world shifted, and STOC adapted, becoming a virtual/online affair in 2020 and 2021. Italy welcomed it in 2022. For the vast majority of its existence, however, from 1969 to 2023, the United States has been its home.

It has also been a significant component of the Federated Computing Research Conference (FCRC) in 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019, and 2023. This collaboration signifies a broader commitment to advancing the field, a pooling of resources and minds under a larger umbrella.

The Oracles: Invited Speakers and Their Declarations

The invited talks at STOC are not mere filler; they are pronouncements from the high priests of computation.

2004

  • Éva Tardos illuminated the complex interplay of "Network games." [8] A topic that resonates deeply in our increasingly interconnected, and often contentious, world.
  • Avi Wigderson posed a question that cuts to the very core of intellectual curiosity: "Depth through breadth, or why should we attend talks in other areas?" [9] A challenge to intellectual silos, a plea for cross-pollination.

2005

  • Lance Fortnow paid homage to the legacy of Larry Stockmeyer with his talk, "Beyond NP: the work and legacy of Larry Stockmeyer." [10] A deep dive into the enduring impact of a significant mind.

2006

  • Prabhakar Raghavan charted the evolving landscape of "The changing face of web search: algorithms, auctions and advertising." [11] A look at how theory meets the messy reality of the digital marketplace.
  • Russell Impagliazzo delved into a fundamental question of computational power: "Can every randomized algorithm be derandomized?" [12] A classic problem, eternally fascinating.

2007

  • Nancy Lynch provided a comprehensive overview of "Distributed computing theory: algorithms, impossibility results, models, and proofs." [13] A foundational pillar of modern computing.

2008

  • Jennifer Rexford offered a critical perspective on "Rethinking internet routing." [14] A look at the invisible infrastructure that governs our digital lives.
  • David Haussler explored a profound evolutionary question: "Computing how we became human." [15] Bridging computation and biology in a way that’s both humbling and awe-inspiring.
  • Ryan O'Donnell presented "Some topics in analysis of boolean functions." [16] A deep dive into the mathematical underpinnings of logic and computation.

2009

  • Shafi Goldwasser delivered the Athena lecture, posing a critical query: "Controlling Access to Programs?" [17] A thought-provoking look at intellectual property and computational security.

2010

  • David S. Johnson delivered the Knuth Prize Lecture, focusing on "Approximation Algorithms in Theory and Practice." [18] A discussion of how we tackle problems that defy exact solutions.

2011

  • Leslie G. Valiant, recipient of the 2010 ACM Turing Award, shared his insights on "The Extent and Limitations of Mechanistic Explanations of Nature." [19] A philosophical exploration grounded in computational principles.
  • Ravi Kannan, honored with the 2011 Knuth Prize, spoke on "Algorithms: Recent Highlights and Challenges." [20] A look at the cutting edge and the road ahead.
  • David A. Ferruci presented on "IBM's Watson/DeepQA," a significant moment in the history of artificial intelligence, during the FCRC Plenary Talk.
  • Luiz Andre Barroso discussed "Warehouse-Scale Computing: Entering the Teenage Decade," also at the FCRC Plenary. [21] A look at the infrastructure that powers our digital world.

2013

2014

  • Thomas Rothvoss presented "The matching polytope has exponential extension complexity."
  • Shafi Goldwasser, a Turing Award laureate, offered "The Cryptographic Lens" (Turing Award Lecture). [24] A perspective on security through the lens of theoretical computation.
  • Silvio Micali, another Turing Award winner, shared his views in "Proofs according to Silvio" (Turing Award Lecture). [25]

2015

  • Michael Stonebraker, a Turing Award recipient, delivered his lecture. [26]
  • Andrew Yao delivered an FCRC Keynote Lecture. [27]
  • László Babai delivered the Knuth Prize Lecture. [28]
  • Olivier Temam gave an FCRC Keynote Lecture.

2016

  • Santosh Vempala spoke on "The Interplay of Sampling and Optimization in High Dimension" (Invited Talk). [29]
  • Timothy Chan discussed "Computational Geometry, from Low to High Dimensions" (Invited Talk). [30]

2017

  • Avi Wigderson delivered a Keynote Talk on "On the Nature and Future of ToC." [31] A visionary look at the field's trajectory.
  • Orna Kupferman presented "Examining classical graph-theory problems from the viewpoint of formal-verification methods" (Keynote Talk). [32]
  • Oded Goldreich delivered the Knuth Prize Lecture. [33]

Connections and Context: See Also

For those who crave more structured knowledge, or perhaps just wish to get lost in the labyrinth of academic discourse:

The Footnotes: Proof and Disclaimers

[1] "Proceedings of the 44th symposium on Theory of Computing." 2012. Retrieved 2012-09-17. [2] "Conference Ranks." Retrieved 2016-08-30. [3] "STOC Conference Best Paper Awards." Retrieved 2012-04-07. [4] "Danny Lewin Best Student Paper Award." Archived from the original on 2008-06-20. [5] Leighton, Tom (2002). "Remarks made by Tom Leighton to commemorate the naming of the STOC Best Student Paper Award in honor of the late Daniel Lewin." [6] Proc. STOC 1969. doi:10.1145/800169. [7] Cook, Stephen (1971), "The complexity of theorem proving procedures" (PDF), Proc. STOC 1971 , pp. 151–158, doi:10.1145/800157.805047, S2CID:7573663. [8] Éva Tardos (2004), "Network games", Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 , pp. 341–342, doi:10.1145/1007352.1007356, ISBN:978-1581138528), S2CID:18249534. [9] Avi Wigderson (2004), "Depth through breadth, or why should we attend talks in other areas?", Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 , p. 579, doi:10.1145/1007352.1007359, ISBN:978-1581138528), S2CID:27563516. [10] Lance Fortnow (2005), "Beyond NP: the work and legacy of Larry Stockmeyer", Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05 , p. 120, doi:10.1145/1060590.1060609, ISBN:978-1581139600), S2CID:16558679. [11] Prabhakar Raghavan (2006), "The changing face of web search: algorithms, auctions and advertising", Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06 , p. 129, doi:10.1145/1132516.1132535, ISBN:978-1595931344), S2CID:19222958. [12] Russell Impagliazzo (2006), "Can every randomized algorithm be derandomized?", Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06 , pp. 373–374, doi:10.1145/1132516.1132571, ISBN:978-1595931344), S2CID:22433370. [13] Nancy Lynch (2007), "Distributed computing theory: algorithms, impossibility results, models, and proofs", Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 , p. 247, doi:10.1145/1250790.1250826, ISBN:9781595936318), S2CID:22140755. [14] Jennifer Rexford (2008), "Rethinking internet routing", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08 , pp. 55–56, doi:10.1145/1374376.1374386, ISBN:9781605580470), S2CID:10958242. [15] David Haussler (2008), "Computing how we became human", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08 , pp. 639–640, doi:10.1145/1374376.1374468, ISBN:9781605580470), S2CID:30452365. [16] Ryan O'Donnell (2008), "Some topics in analysis of boolean functions", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08 , pp. 569–578, doi:10.1145/1374376.1374458, ISBN:9781605580470), S2CID:1241681. [17] Shafi Goldwasser (2009), "Athena lecture: Controlling Access to Programs?", Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09 , pp. 167–168, doi:10.1145/1536414.1536416, ISBN:9781605585062). [18] David S. Johnson (2010), "Approximation Algorithms in Theory and Practice" (Knuth Prize Lecture). [19] Leslie G. Valiant (2011), "The Extent and Limitations of Mechanistic Explanations of Nature" (2010 ACM Turing Award Lecture). [20] Ravi Kannan (2011), "Algorithms: Recent Highlights and Challenges" (2011 Knuth Prize Lecture). [21] Luiz Andre Barroso (2011), "Warehouse-Scale Computing: Entering the Teenage Decade" (FCRC Plenary Talk). [22] Gary Miller (2013), Knuth Prize Lecture. [23] Prabhakar Raghavan (2013), Plenary talk. [24] Shafi Goldwasser (2014), "The Cryptographic Lens" (Turing Award Lecture) video. [25] Silvio Micali (2014), "Proofs according to Silvio" (Turing Award Lecture) video. [26] Michael Stonebraker (2015), Turing Award Lecture video. [27] Andrew Yao (2015), FCRC Keynote Lecture. [28] László Babai (2015), Knuth Prize Lecture. [29] Santosh Vempala (2016), "The Interplay of Sampling and Optimization in High Dimension" (Invited Talk). [30] Timothy Chan (2016), "Computational Geometry, from Low to High Dimensions" (Invited Talk). [31] Avi Wigderson (2017), "On the Nature and Future of ToC" (Keynote Talk). [32] Orna Kupferman (2017), "Examining classical graph-theory problems from the viewpoint of formal-verification methods" (Keynote Talk). [33] Oded Goldreich (2017), Knuth Prize Lecture.