The 2004 Gödel Prize for outstanding journal articles in theoretical computer science is shared between the papers:
"The Topological Structure of Asynchronous Computation"and
by Maurice Herlihy and Nir Shavit,
Journal of the ACM, Vol. 46 (1999), 858-923,
"Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge"
by Michael Saks and Fotios Zaharoglou,
SIAM J. on Computing, Vol. 29 (2000), 1449-1483.
The two papers recognized by the 2004 Gödel Prize offer one of the most important breakthroughs in the theory of distributed computing.
The problem attacked is the complete understanding of asynchronous wait-free deterministic computation in the basic shared memory model. These papers demonstrate that one can avoid the inherent difficulty of analyzing a dynamic model, transforming it into a static one by associating computational tasks with simplicial complexes and translating the question of existence of a wait-free protocol into (distinct but related) topological questions about the complexes. This reformulation allows the introduction of powerful topological invariants, such as homologies, to show the impossibility of numerous tasks, including set-agreement and renaming.
The discovery of the topological nature of distributed computing
provides a new perspective on the area and represents one of the most
striking examples, possibly in all of applied mathematics, of the use of
topological structures to quantify natural computational phenomena.
The Gödel Prize for outstanding papers in the area of theoretical
computer science is sponsored jointly by the European Association for Theoretical
Computer Science (EATCS) and the Special Interest Group on Algorithms and
Computing Theory of the Association of Computing Machinery (ACM-SIGACT).
This award is presented annually, with the presentation taking place alternately
at the International Colloquium on Automata, Languages, and Programming
(ICALP) and ACM Symposium on the Theory of Computing (STOC). The twelfth
presentation will take place during the 2004 ICALP, July 2004 in Turku,
Finland. The Prize is named in honor of Kurt Gödel in recognition
of his major contributions to mathematical logic and of his recently discovered
interest in what has become the famous "P versus NP" question. The Prize
includes an award of $5000 (US).
AWARD COMMITTEE: 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, with the 2004 Chair being an EATCS representative. The 2004 Award Committee consists of Giorgio Ausiello (University of Rome "La Sapienza"), László Babai (University of Chigaco), Pierre-Louis Curien (CNRS, Paris 7), Zvi Galil (Columbia University), Juhani Karhumäki (Chair, University of Turku) and Jeff Ullman (Stanford University).
ELIGIBILITY: Any research paper or a series of papers published (not reprinted) in a recognized refereed journal by a single author or a team of authors in the period 1997-2003 is eligible. This extended period is in recognition of the fact that the value of fundamental work cannot always be immediately assessed. The research nominated for the award should be in the area of theoretical computer science. The term "theoretical computer science" is meant in a broad sense, and encompasses, but is not restricted to, those areas covered by ICALP and STOC. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.
NOMINATIONS: Nominations for the award should be submitted to the Award Committee Chair at the following address:
Professor Juhani KarhumäkiTo be considered, nominations for the 2004 prize must be received by January 10, 2004. Nominations may be made by any member of the scientific community. A nomination should contain a brief summary of the technical content of the paper and a brief explanation of its significance. A copy of the research paper or papers should accompany the nomination. The work may be in any language. However, if it is not in English, a more extended summary written in English should be enclosed. Additional recommendations in favor of the nominated work may also be enclosed. To be considered for the award, the paper or series of papers must be recommended by at least two individuals, either in the form of two distinct nominations or one nomination including recommendations from two different people.
Department of Mathematics & Turku Centre for Computer Science
University of Turku
20014 University of Turku, FINLAND
email: karhumak@cs.utu.fi
tel.: 358-2-333 5613
fax: 358-2-333 6595
It is the duty of the Award Committee to actively solicit nominations from as broad a spectrum of the theoretical computer science community as possible, so as to ensure that potential award-winning papers are not overlooked. To this end, the Award Committee will accept informal proposals of potential nominees, as well as tentative offers to prepare formal nominations, should they be needed to fulfill the requirements that the paper have two separate recommendations.
SELECTION PROCESS: Although the Award Committee is encouraged to consult with the theoretical computer science community at large, the Award Committee is solely responsible for the selection of the winner of the award. In the case that the Award Committee cannot agree on a recipient, the prize may be shared by more than one paper or series of papers, and the Award Committee reserves the right to declare no winner at all. All matters relating to the selection process that are not specified here are left to the discretion of the Award Committee.
PAST WINNERS:
1993:
László Babai and Shlomo Moran, "Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes," Journal of Computer and System Sciences 36 (1988), 254-276.Shafi Goldwasser, Silvio Micali and Charles Rackoff, "The knowledge complexity of interactive proof systems," SIAM Journal on Computing 18 (1989), 186-208.
1994:
Johan Håstad, "Almost optimal lower bounds for small depth circuits," Advances in Computing Research 5 (1989), 143-170.
1995:
Neil Immerman, "Nondeterministic space is closed under complementation," SIAM Journal on Computing 17 (1988), 935-938.Róbert Szelepcsényi, "The method of forced enumeration for nondeterministic automata," Acta Informatica 26 (1988), 279-284.
1996:
Alistair Sinclair and Mark Jerrum, "Approximate counting unform generation and rapidly mixing Markov chains," Information and Computation 82 (1989), 93-133.Mark Jerrum and Alistair Sinclair, "Approximating the permanent," SIAM Journal on Computing 18 (1989), 1149-1178.
1997:
Joseph Halpern and Yoram Moses, "Knowledge and common knowledge in a distributed environment," Journal of the ACM 37 (1990), 549-587.
1998:
Seinosuke Toda, "PP is as hard as the polynomial-time hierarchy," SIAM Journal on Computing 20 (1991), 865-877.
1999:
Peter W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM Journal on Computing26 (1997), 1484-1509.
2000:
Moshe Y. Vardi and Pierre Wolper, "Reasoning about infinite computations," Information and Computation 115 (1994), 1-37.
2001:
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy, "Interactive proofs and the hardness of approximating cliques," Journal of the ACM 43 (1996), 268-292.Sanjeev Arora and Shmuel Safra, "Probabilistic checking of proofs: a new characterization of NP," Journal of the ACM 45 (1998), 70-122.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, "Proof verification and the hardness of approximation problems," Journal of the ACM 45 (1998), 501-555.
2002:
Géraud Sénizergues, "L(A)=L(B)? Decidability results from complete formal systems," Theoretical Computer Science 251 (2001), 1-166.
2003:
Yoav Freund and Robert Schapire, "A Decision Theoretic Generalization of On-Line Learning and an Application to Boosting," Journal of Computer and System Sciences 55 (1997), 119-139.