ACM-SIAM Symposium on Discrete Algorithms (SODA04)
Chair: Ian Munro, University of Waterloo
Astor Crowne Plaza Hotel
New Orleans, LA
January 11-13, 2004

Jointly sponsored by ACM Special Interest Group on Algorithms and Computation Theory and SIAM Activity Group on Discrete Mathematics


Immediately preceding the conference at the same location, The 6th Workshop on Algorithm Engineering and Experiments (ALENEX 04) and the 1st Workshop on Analytic Algorithmics and Combinatorics (ANALCO04).

Immediately following the conference at the same location, Workshop on Dynamic Algorithms and Applications.

About the Symposium

This symposium focuses on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations. Performance analyses may be analytical or experimental and may address worst-case or expected-case performance. Studies can be theoretical or based on data sets that have arisen in practice and may address methodological issues involved in performance analysis.

Conference Themes

Themes and application areas include, but are not limited to, the following topics:

*Combinatorics and other aspects of Discrete Mathematics such as:

*other aspects of Computer Science such as:

*and applications in the Sciences and Business such as: Biology, Physics, and Finance.

Program Committee

Ian Munro, University of Waterloo, Canada (chair)
Susanne Albers, Universität Freiburg, Germany
Lars Arge, Duke University
Gerth Brodal, University of Århus, Denmark
Adam Buchsbaum, AT&T Labs - Research
Lenore Cowen, Tufts University
Martin Farach-Colton, Rutgers University
Alan Frieze, Carnegie Mellon University
Andrew Goldberg, Microsoft Research
John Hershberger, Mentor Graphics
Mark Jerrum, University of Edinburgh, United Kingdom
David Johnson, AT&T Labs - Research
Rao Kosaraju, Johns Hopkins University
Alejandro López-Ortiz, University of Waterloo, Canada
Michele Mosca, University of Waterloo, Canada and Perimeter Institute
S. Muthukrishnan, AT&T Labs - Research and Rutgers University
Günter Rote, Freie Universität, Berlin, Germany
Frank Ruskey, University of Victoria, Canada
Jeremy Spinrad, Vanderbilt University
Cliff Stein, Columbia University
Subhash Suri, University of California, Santa Barbara

Invited Plenary Speakers

Who Says You Have to Look at the Input? The Brave New World of Sublinear Computing?
Bernard Chazelle, Princeton University and NEC Laboratories America, Inc.

Quantum Computing
Raymond Laflamme, Institute for Quantum Computing, University of Waterloo, Canada, and Perimeter Institute for Theoretical Physics, Waterloo, Canada

How Random is the Human Genome?
Peter Winkler, Bell Laboratories, Lucent Technologies

Deadline for Submissions

Submissions are due July 3, 2003, no later than 5:00 PM Eastern Time. Submissions received after this time will not be considered.

How to Participate

Submission of Papers

To see the full details of the mechanics and to do the actual submission, visit The deadline for submission is 5:00 PM Eastern Time, July 3, 2003.

Selection of Papers
Selection of papers will be based on the extent to which the results yield new insights for the design, use, or analysis of efficient algorithms. The program committee encourages submissions from researchers in the discrete mathematics and experimental and applied algorithms communities. Submissions from the discrete mathematics community may address the design and analysis of algorithms for discrete structures or the development of algorithms as tools for investigating significant open questions in mathematics.

Experimental and applied submissions may deal, for example, with efficient implementation of fundamental algorithms or with heuristics for basic difficult problems. They should provide new and significant insights into algorithmic performance and/or design or discuss the methodology of doing experimental performance analysis. Applied papers should deal with algorithms applied in a specific practical setting and should include convincing evidence that the algorithms or data structures discussed are useful and efficient in the particular context.

Two types of submissions are allowed: "long form abstracts" and "short form abstracts".

Long form submissions are the customary extended abstracts and should report on original research that has not been published elsewhere nor concurrently submitted to another conference with proceedings. Accepted long form submissions will be allotted ten pages in the proceedings.

Short form submissions will also be reviewed by the program committee, but we expect to accept a broader range of papers in this category. We encourage submissions of the customary type that fit into this page limit to be submitted in this form; we also seek submissions that report on partial results and work-in-progress. Accepted short form submissions will be allotted two pages in the proceedings.

Submission Formats
Submissions should begin with the title of the paper, each author's name, affiliation, and e-mail address, followed by a succinct statement of the problems that are considered in the paper, the main results, an explanation of the significance of the work, and a comparison to past research. This material should be easily understood by nonspecialists. Technical developments, directed toward the specialist, should follow as appropriate. For long submissions, the entire extended abstract must not exceed 12 pages; for short submissions, 3 pages. In either case, the page bound includes the bibliography and title page. Use 11 point or larger font in single column format, with not less than one inch margins all around.

Submissions that deviate significantly from these guidelines risk rejection without consideration of their merits.

Simultaneous Submissions
Abstract material which has been previously published in another conference proceedings or journal (or which is scheduled for publication prior to SODA) will not be considered for acceptance at SODA. In addition, SODA conference policy does not allow simultaneous submissions of the same (or essentially the same) abstract material to another conference with a published proceedings.

Best Student Paper Award
A prize of $500 will be awarded to the author(s) of the best student-authored paper (or split between more than one paper if there is a tie). A paper is eligible if all of its authors are full-time students at the time of submission. This must be indicated in the submission process.

Congratulations! Best Student Paper Award Winner
" Correlation Clustering: Maximizing Agreements via Semidefinite Programming"
Chaitanya Swamy, Cornell University

Author Notification
Acceptance/rejection notices will be sent to authors via e-mail in early September.

Paper Presenters
The Program Committee expects every speaker of a scheduled presentation to pre-register and attend the symposium. Each speaker will be allotted twenty minutes for presentation.

If it becomes necessary for a speaker to cancel a presentation, he or she must find an alternate presenter, preferably a co-author. The SIAM Conference Department must be informed of any change to a scheduled presentation. A "no-show" or cancelled presentation can cause serious inconvenience to the attendees and symposium organizers. The committee thanks all speakers in advance for their compliance with this request.

Symposium Proceedings

SIAM will send instructions for paper preparation to authors of accepted papers. A copy of each accepted paper, in the requested format, must reach the SIAM office by October 6, 2003 by 5:00 PM Eastern Time; otherwise, the papers may not be included in the proceedings. The proceedings will be available at the symposium.

General Information

Registration and Hotel information are now available! Visit here for transportation information and here for the hotel room sharing form.

NEW!IBM logo

IBM Research Sponsors Student Travel Grants to SODA04 Award

Four awards of $500 each will be granted toward travel to SODA04. To Qualify:

Any full-time student in good standing is eligible to receive an award plus gratis meeting registration. Top priority will be given to students presenting papers at the meeting, with second priority to students who are co-authors of papers to be presented at the meetings. An application for a travel award must include:

1. A letter from the student describing his/her academic standing and interests, his/her expected graduation date and degree, advisor's name, and, if available, a URL for a working Web page.
2. If applicable, the title(s) of the paper(s) to be presented by the student (author or co-author) at the meeting.
3. A detailed expense list, in US dollars.
4. Other travel funds that are available to you (optional).
5. Statement from your advisor on availability of funds, indicating why the student is deserving of receiving a travel fund, and any special circumstances.

Complete applications must be received at the SIAM office no later than December 8, 2003.
Winner will be notified by December 18, 2003. Checks for the awards will be given to the winning students when they arrive at the meeting and check in at the SIAM Registration Desk.

A SIAM committee will select the awardees. The list of winners will be submitted to IBM Research.
Applications should be sent to the following address:

Attention: Joanna Littleton, IBM Research Student Travel Award, SODA 04
3600 University City Science Center
Philadelphia, PA 19104-2688.
Students also may apply by e-mail to [email protected] or by fax to 215-386-7999.


Publishers, software and hardware suppliers, service organizations, and others having products or services to offer are invited to participate in the exhibition. For further information and fees, please contact the SIAM Marketing Representative at [email protected].