The Gödel Prize is an annual prize for outstanding papers in the area of
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, given jointly by the
European Association for Theoretical Computer Science (EATCS) and the
Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (
ACM SIGACT
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
Publi ...
). The award is named in honor of
Kurt Gödel. 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
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...
in which Gödel asked whether a certain
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
problem could be solved in
quadratic or
linear time.
The Gödel Prize has been awarded since 1993. The prize is awarded either at STOC (ACM
Symposium on Theory of Computing The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for ...
, one of the main
North American
North America is a continent in the Northern Hemisphere and almost entirely within the Western Hemisphere. It is bordered to the north by the Arctic Ocean, to the east by the Atlantic Ocean, to the southeast by South America and the Ca ...
conferences in theoretical computer science) or ICALP (
, one of the main
Europe
Europe is a large peninsula conventionally considered a continent in its own right because of its great physical size and the weight of its history and traditions. Europe is also considered a subcontinent of Eurasia and it is located entirel ...
an 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 prize includes a reward of US$5000.
The winner of the Prize is selected by a committee of six members. 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.
In contrast with the Gödel Prize, which recognizes outstanding papers, the
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
History
The Knuth Prize has been awarded since 1996 and includes an award of U ...
is awarded to individuals for their overall impact in the field.
Recipients
Winning papers
See also
*
List of computer science awards
Notes
References
Prize website with list of winners
{{DEFAULTSORT:Godel Prize
Theoretical computer science
Computer science awards
Awards established in 1993
Annual events