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 Sciences36(1988), 254-276.Shafi Goldwasser, Silvio Micali and Charles Rackoff, "The knowledge complexity of interactive proof systems,"

SIAM Journal on Computing18(1989), 186-208.

1994:

Johan Håstad, "Almost optimal lower bounds for small depth circuits,"Advances in Computing Research5(1989), 143-170.

1995:

Neil Immerman, "Nondeterministic space is closed under complementation,"SIAM Journal on Computing17(1988), 935-938.Róbert Szelepcsényi, "The method of forced enumeration for nondeterministic automata,"

Acta Informatica26(1988), 279-284.

1996:

Alistair Sinclair and Mark Jerrum, "Approximate counting unform generation and rapidly mixing Markov chains,"Information and Computation82(1989), 93-133.Mark Jerrum and Alistair Sinclair, "Approximating the permanent,"

SIAM Journal on Computing18(1989), 1149-1178.

1997:

Joseph Halpern and Yoram Moses, "Knowledge and common knowledge in a distributed environment,"Journal of the ACM37(1990), 549-587.

1998:

Seinosuke Toda, "PP is as hard as the polynomial-time hierarchy,"SIAM Journal on Computing20(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 Computation115(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 ACM43(1996), 268-292.Sanjeev Arora and Shmuel Safra, "Probabilistic checking of proofs: a new characterization of NP,"

Journal of the ACM45(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 ACM45(1998), 501-555.

2002:

Géraud Sénizergues, "L(A)=L(B)? Decidability results from complete formal systems,"Theoretical Computer Science251(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 Sciences55(1997), 119-139.