Simpósio da Teoria da Computação

STOC, o Simpósio Anual da ACM de Teoria da Computação é uma conferência acadêmica no campo da teoria da ciência da computação. O STOC vem sendo realizado anualmente desde 1969, o qual é normalmente realizado em Maio ou Junho. A conferência é promovida pelo SIGACT, um grupo especial da  ACM. As taxas de aprovação do STOC pela comunidade científica calculadas a partir de 1970 até 2012 são em média 31%, com uma taxa de 29% de aprovação em 2012.

Como Fich (1996) escreveu, o STOC e sua contrapartida do IEEE, o FCOS (Simpósio de Fundamentos da Ciência da Computação), são considerados amplamente as duas melhores conferências de informática teórica do mundo: "são fóruns de discussão de alguns dos melhores trabalhos de toda a teoria da computação, promovem uma amplitude de conhecimento entre os pesquisadores da teoria da computação e ajudam a manter a comunidade científica unida." Johnson (1984) inclui a frequência regular no STOC e FCOS como uma das várias características decisoras do perfil dos cientistas da teoria da computação

Prêmios

O Prêmio Gödel para trabalhos excepcionais na teoria da ciência da computação é apresentado alternadamente no STOC e no Colóquio Internacional de Autômatos, Linguagens e Programação (ICALP); o Prêmio Knuth por contribuições excepcionais para informática teórica é apresentado alternadamente no STOC e no FOCS.

Desde 2003, o STOC tem apresentado um ou mais Prêmios de Melhor artigo científico para premiar os melhores artigos científicos da conferência. Além disso, o Prêmio Danny Lewin do melhor artigo de estudante é concedido aos autores do melhor artigo feito por estudantes no STOC; o prêmio é denominado em homenagem a Daniel M. Lewin. A contrapartida do FOCS para o prêmio Danny Lewin é o Prêmio Machtey.

História

O Simpósio da Teoria da Computação (STOC) foi organizado pela primeira vez de 5 a 7 de Maio de 1969, em Marina del Rey, Califórnia, Estados Unidos. O presidente da conferência foi Patrick C. Fischer, e o comitê de programa do STOC consistiu de Michael A. Harrison, Robert W. Floyd, Juris Hartmanis, Richard M. Karp, Albert R. Meyer, e Jeffrey D. Ullman.

Um dos primeiros artigos científicos do STOC incluem o de Cook (1971), que introduziu o conceito de NP-completude (Teorema de Cook–Levin).

O STOC foi organizado no Canadá, em 1992, 1994, 2002 e 2008, e na Grécia, em 2001; todas as outras reuniões de 1969-2009 foram realizadas nos Estados Unidos. O STOC fazia parte da Federated Computing Research Conference (FCRC) em 1993, 1996, 1999, 2003, 2007, e 2011.

Palestrantes convidados

2004

Éva Tardos (2004), «Network games», Network games, doi:10.1145/1007352.1007356 

Avi Wigderson (2004), «Depth through breadth, or why should we attend talks in other areas?», Depth through breadth, or why should we attend talks in other areas?, doi:10.1145/1007352.1007359 

2005

Lance Fortnow (2005), «Beyond NP: the work and legacy of Larry Stockmeyer», Beyond NP, doi:10.1145/1060590.1060609 

2006

Prabhakar Raghavan (2006), «The changing face of web search: algorithms, auctions and advertising», The changing face of web search, doi:10.1145/1132516.1132535 

Russell Impagliazzo (2006), «Can every randomized algorithm be derandomized?», Can every randomized algorithm be derandomized?, doi:10.1145/1132516.1132571 

2007

Nancy Lynch (2007), «Distributed computing theory: algorithms, impossibility results, models, and proofs», Distributed computing theory, doi:10.1145/1250790.1250826 

2008

Jennifer Rexford (2008), «Rethinking internet routing», Rethinking internet routing, doi:10.1145/1374376.1374386 

David Haussler (2008), «Computing how we became human», Computing how we became human, doi:10.1145/1374376.1374468 

Ryan O'Donnell (2008), «Some topics in analysis of boolean functions», Some topics in analysis of boolean functions, doi:10.1145/1374376.1374458 

2009

Shafi Goldwasser (2009), «Athena lecture: Controlling Access to Programs?», Athena lecture, doi:10.1145/1536414.1536416 

Ver também

• Conferências em informática teórica.

Referências

• Cook, Stephen (1971), «The complexity of theorem proving procedures», Proc. STOC 1971, pp. 151–158, doi:10.1145/800157.805047 .
• Fich, Faith (1996), «Infrastructure issues related to theory of computing research», ACM Computing Surveys, 28 (4es), doi:10.1145/242224.242502 .
• Johnson, D. S. (1984), «The genealogy of theoretical computer science: a preliminary report», ACM SIGACT News, 16 (2): 36–49, doi:10.1145/1008959.1008960 .

Ligações externas

• STOC site
• «STOC proceedings information». in DBLP. 
• «STOC proceedings». in the ACM digital library. 
• Citation Statistics for FOCS/STOC/SODA, Piotr Indyk and Suresh Venkatasubramanian, July 2007.