Call for Participation THE THIRD DIMACS INTERNATIONAL ALGORITHM IMPLEMENTATION CHALLENGE In conjunction with its Special Year on Parallel Computing, the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) invites participation in an international Implementation Challenge to study effective parallel algorithms for combinatorial problems. The Implementation Challenge will take place between November 1993 and September 1994. Participants are invited to carry out research projects related to the problem areas specified below and to present research papers at a DIMACS workshop to be held in October 1994. A refereed workshop proceedings will be published. RESEARCH PROJECTS. The use of massive parallelism in discrete combinatorial applications has received far less attention than numerical applications. Despite the large body of theoretical work on parallel algorithms for combinatorial problems, it is unclear what kinds of parallel algorithms will be most effective in practice. The goal of this challenge is to provide a forum for a concerted effort to study effective algorithms for combinatorial problems, and to investigate the opportunities for massive speedups on parallel computers. The challenge will include two problem areas for research study. 1. Tree searching algorithms Examples: game trees, combinatorial optimization. 2. Parallel algorithms for sparse and dynamic graphs Examples: minimum spanning trees, shortest paths. Participants are welcome to select applications other than the examples given above. The aim should be to pick an application which presents clear technical obstacles to naive parallelization, and to pick large problem instances to warrant the use of massive parallelism. DIMACS SUPPORT. The DIMACS advisory committee will provide feedback on proposals, and DIMACS facilities will serve as a clearing house for exchange of programs and communication among researchers. DIMACS cannot provide financial support for research projects. DIMACS is currently investigating possibilities for participants to access massively parallel processors at the NSF Supercomputing Centers across the US. HOW TO PARTICIPATE. For more information about participating in the Implementation Challenge, send a request for the document "General Information" (available November 15, 1993) to challenge3@dimacs.rutgers.edu. Request either LaTeX format (sent through email) or hard copy (sent through U. S. Mail), and include your return address as appropriate. Challenge materials will also be available via anonymous FTP from DIMACS, and we expect most communication with respect to the Challenge to take place over the Internet. ADVISORY BOARD. A committee of DIMACS members will provide general direction for the Implementation Challenge. Committee members include Sandeep Bhatt, Bellcore and Rutgers University (Coordinator), David Culler, U.C. Berkeley, David Johnson, ATT-Bell Laboratories, Lennart Johnsson, Thinking Machines Corporation and Harvard University, Charles Leiserson, MIT, and Pangfeng Liu, DIMACS.