Gödel Prize
Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.STOC is the ACM Symposium on Theory of Computing, one of the main North American conferences in theoretical computer science, whereas ICALP is the International Colloquium on Automata, Languages and Programming, one of the main European conferences in the field.To be eligible for the prize, a paper must be published in a refereed journal within the last 14 (formerly 7) years.The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms.The committee is chaired alternately by representatives of EATCS and SIGACT.
Gödel Lecturetheoretical computer scienceEuropean Association for Theoretical Computer ScienceAssociation for Computing MachineryACM SIGACTKurt GödelP versus NPJohn von NeumannNP-completequadraticlinear timeSymposium on Theory of ComputingNorth AmericanInternational Colloquium on Automata, Languages and ProgrammingEuropeanKnuth PrizeLászló BabaiShafi GoldwasserSilvio MicaliShlomo MoranCharles Rackoffinteractive proof systemsJohan Håstadlower boundthe size ofBoolean circuitsparity functionNeil ImmermanRóbert SzelepcsényiImmerman–Szelepcsényi theoremMark JerrumAlistair SinclairMarkov chainspermanent of a matrixJoseph HalpernYoram MosesSeinosuke TodaToda's theoremPeter ShorShor's algorithmfactoringpolynomial timequantum computerMoshe Y. VardiPierre Wolpertemporal logicfinite automataSanjeev AroraUriel FeigeCarsten LundLászló LovászRajeev MotwaniShmuel SafraMadhu SudanMario SzegedyPCP theoremGéraud Sénizerguesdeterministic pushdown automatadecidableYoav FreundRobert SchapireAdaBoostmachine learningMaurice HerlihyMichael SaksNir ShavitFotios Zaharogloutopologydistributed computingNoga AlonYossi Matiasstreaming algorithmsManindra AgrawalNeeraj KayalNitin SaxenaAKS primality testAlexander RazborovSteven Rudichnatural proofsDaniel SpielmanShang-Hua Tengsmoothed analysisOmer ReingoldSalil VadhanAvi Wigdersonzig-zag productgraphsundirected connectivitylog spaceJoseph S. B. Mitchellpolynomial-time approximation schemeTravelling Salesman ProblemElias KoutsoupiasChristos PapadimitriouNoam NisanAmir RonenTim RoughgardenÉva Tardosalgorithmic game theoryDan BonehMatthew K. FranklinAntoine JouxDiffie–Hellman key exchangeBoneh–Franklin schemeRonald FaginMoni NaormiddlewarePeter W. O'HearnCynthia DworkFrank McSherryKobbi NissimAdam D. Smithdifferential privacyOded Regevlearning with errorsIrit DinurGábor Tardosconstructive proofLovász local lemmaJin-Yi CaiXi ChenMartin Dyercounting complexityconstraint satisfaction problemsZvika BrakerskiCraig Gentry