Symposium über die Computertheorie

Das Jährliches ACM -Symposium über die Theorie des Computers (Stoc) ist ein Akademische Konferenz auf dem Gebiet der Theoretische Informatik. STOC wird seit 1969 jährlich organisiert, normalerweise im Mai oder Juni; Die Konferenz wird von der gesponsert Verband für Rechenmaschinen Besondere Interessengruppe Sigakt. Die Akzeptanzrate von STOC, gemittelt von 1970 bis 2012, beträgt 31% mit der Rate von 29% im Jahr 2012.[1]

Wie Fich (1996) schreibt, stoc und sein jährliches IEEE Gegenstückszellen (die Symposium über Fundamente der Informatik) werden als die beiden Top -Konferenzen in der theoretischen Informatik angesehen,[2] Im Großen und Ganzen sind sie „Foren für einige der besten Arbeiten während der gesamten Computertheorie, die die Breite unter Theorie der Computerforscher fördern und dazu beitragen, die Gemeinschaft zusammenzuhalten.“ Johnson (1984) Beinhaltet regelmäßige Besucherzahlen bei STOC und FOCS als eines von mehreren definierenden Merkmalen theoretischer Informatiker.

Auszeichnungen

Das Gödel -Preis Für herausragende Papiere in der theoretischen Informatik wird abwechselnd bei STOC und im Internationales Kolloquium über Automaten, Sprachen und Programmierung (ICICP); das Knuth -Preis Für herausragende Beiträge zu den Grundlagen der Informatik wird abwechselnd bei STOC und bei vorgestellt Fugen.

Seit 2003 hat STOC eine oder mehrere beste Papierpreise übergeben[3] Anerkennung von Arbeiten von höchster Qualität auf der Konferenz. Darüber hinaus wird der Danny Lewin Best Student Paper Award an die Autoren des besten studentisch-autorierten Papiers in STOC verliehen.[4] Die Auszeichnung ist zu Ehren von von genannt Daniel M. Lewin, ein amerikanisch-israelischer Mathematiker und Unternehmer, der Mitbegründer der Internet-Firma Akamai Technologiesund war eines der ersten Opfer der 11. September Angriffe.[5]

Geschichte

STOC wurde erstmals am 5. bis 7. Mai 1969 in organisiert Marina del Rey, Kalifornien, Vereinigte Staaten. Der Konferenzvorsitzende war Patrick C. Fischerund das Programmkomitee bestand aus Michael A. Harrison, Robert W. Floyd, Juris Hartmanis, Richard M. Karp, Albert R. Meyer, und Jeffrey D. Ullman.[6]

Frühe Samenpapiere in STOC sind einzuziehen Cook (1971), was das Konzept von einführte NP-Vervollständigung (siehe auch Cook -Levin -Theorem).

Ort

STOC wurde in organisiert Kanada 1992, 1994, 2002 und 2008 und in Griechenland in 2001; Alle anderen Treffen in den Jahren 1969–2009 wurden in der abgehalten Vereinigte Staaten. STOC war Teil der Federated Computing Research Conference (FCRC) 1993, 1996, 1999, 2003, 2007 und 2011.

Eingeladene Redner

2004
Éva Tardos (2004), "Netzwerkspiele", Verfahren des sechsunddreißigsten jährlichen ACM -Symposiums über die Theorie des Computers - STOC '04, S. 341–342, doi:10.1145/1007352.1007356, ISBN 978-1581138528
Avi Wigderson (2004), "Tiefe durch Breite oder warum sollten wir in anderen Bereichen Gespräche besuchen?", Verfahren des sechsunddreißigsten jährlichen ACM -Symposiums über die Theorie des Computers - STOC '04, p. 579, doi:10.1145/1007352.1007359, ISBN 978-1581138528
2005
Lance Fortnow (2005), "Beyond NP: Die Arbeit und das Erbe von Larry Stockmeyer", Verfahren des siebenunddreißigjährigen jährlichen ACM -Symposiums über die Theorie des Computers - STOC '05, p. 120, doi:10.1145/1060590.1060609, ISBN 978-1581139600
2006
Prabhakar Raghavan (2006), "Das sich ändernde Gesicht der Websuche: Algorithmen, Auktionen und Werbung", Verfahren des achtunddreißigjährigen ACM -Symposiums über die Theorie des Computers - STOC '06, p. 129, doi:10.1145/1132516.1132535, ISBN 978-1595931344
Russell Impagliazzo (2006): "Kann jeder randomisierte Algorithmus desandomisiert werden?", Verfahren des achtunddreißigjährigen ACM -Symposiums über die Theorie des Computers - STOC '06, p. 373, doi:10.1145/1132516.1132571, ISBN 978-1595931344
2007
Nancy Lynch (2007), "Distributed Computing Theory: Algorithmen, Unmöglichkeitsergebnisse, Modelle und Beweise", Verfahren des neununddreißigsten jährlichen ACM -Symposiums über die Theorie des Computers - STOC '07, p. 247, doi:10.1145/1250790.1250826, ISBN 9781595936318
2008
Jennifer Rexford (2008), "Internet -Routing überdenken", Proceedings of the Fortieth jährlich ACM -Symposium über die Theorie des Computers - STOC 08, S. 55–56, doi:10.1145/1374376.1374386, ISBN 9781605580470
David Hausler (2008), "Berechnung, wie wir menschlich wurden", Proceedings of the Fortieth jährlich ACM -Symposium über die Theorie des Computers - STOC 08, S. 639–640, doi:10.1145/1374376.1374468, ISBN 9781605580470
Ryan O'Donnell (2008), "Einige Themen in der Analyse der Booleschen Funktionen", Proceedings of the Fortieth jährlich ACM -Symposium über die Theorie des Computers - STOC 08, S. 569–578, doi:10.1145/1374376.1374458, ISBN 9781605580470
2009
SHAFI GOLDSER (2009), "Athena Lecture: Kontrolle des Zugangs zu Programmen?", Verfahren des 41. jährlichen ACM -Symposiums über Symposium über die Theorie des Computing - STOC '09, S. 167–168, doi:10.1145/1536414.1536416, ISBN 9781605585062
2010
David S. Johnson (2010), "Näherungsalgorithmen in Theorie und Praxis" (Knuth Prize Lecture)
2011
Leslie G. Valiant (2011), "Das Ausmaß und die Einschränkungen mechanistischer Erklärungen der Natur" (ACM Turing Award Lecture 2010)
Ravi Kannan (2011), "Algorithmen: Jüngste Highlights und Herausforderungen" (2011 KNUTH PRIRET)
David A. Ferruci (2011), "IBMs Watson/Deepqa" (FCRC -Plenargespräch)
Luiz Andre Barroso (2011), "Lager-Scale-Computing: Eintritt in das Teenager-Jahrzehnt" (FCRC-Plenargespräch)
2013
Gary Miller (2013), Knuth Prize Lecture
Prabhakar Raghavan (2013), Plenargespräch
2014
Thomas Rothvoss (2014), "Das passende Polytope hat eine exponentielle Erweiterungskomplexität"
SHAFI GOLDSER (2014), "The Cryptographic Lens" (Turing Award Lecture) Video
Silvio Micali (2014), "Proofs nach Silvio" (Turing Award Lecture) Video
2015
Michael Stonebraker (2015), Turing Award Lecture Video
Andrew Yao (2015), FCRC Keynote Lecture
László Babai (2015), Knuth Prize Lecture
Olivier Temam (2015), FCRC Keynote Lecture
2016
Santosh Vempala (2016), "Das Zusammenspiel von Stichproben und Optimierung in hoher Dimension" (eingeladener Gespräch)
Timothy Chan (2016), "Computergeometrie, von niedrigen bis hohen Dimensionen" (eingeladenes Gespräch)
2017
Avi Wigderson (2017), "Über die Natur und die Zukunft von TOC" (Keynote Talk)
Orna Kuperferman (2017), "Untersuchung klassischer Graphentheorieprobleme aus dem Gesichtspunkt der formalen Überwachungsmethoden" (Keynote Talk)
Od Goldreich (2017), Knuth Prize Lecture

Siehe auch

Anmerkungen

  1. ^ "Verfahren des 44. Symposiums über die Theorie des Computers". 2012. Abgerufen 2012-09-17.
  2. ^ "Konferenz rangiert". Abgerufen 2016-08-30.
  3. ^ "STOC Conference Best Paper Awards". Abgerufen 2012-04-07.
  4. ^ "Danny Lewin Best Student Paper Award". Archiviert von das Original am 2008-06-20.
  5. ^ Leighton, Tom (2002). "Bemerkungen von Tom Leighton zum Gedenken an die Benennung des STOC Best Student Paper Award zu Ehren des verstorbenen Daniel Lewin".
  6. ^ Proc. STOC 1969. doi:10.1145/800169.

Verweise

Externe Links