Fourteehth Annual ACM-SIAM Symposium on Discrete Algorithms

January 12-14, 2003
Hyatt Regency Baltimore, on the Inner Harbour
Baltimore, MD, USA

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 5th Workshop on Algorithm Engineering and Experiments (ALENEX 03) and also the 1st Workshop on Algorithms for Listing, Counting, and Enumeration (ALICE03).

About the Conference

This symposium concerns research on the use, design, and analysis of efficient algorithms and data structures, and on the mathematical problems related to the development and analysis of discrete algorithms. Performance analysis may be analytical or experimental, and may address worst-case or average-case performance. These studies can be theoretical or based on real data sets, and may address methodological issues involved in performance analysis.

Conference Themes

Application areas include, but are not limited to:
Discrete Mathematics and Combinatorics
Combinatorial Structures
Communication Networks
Computational Biology
Computational Physics
Computational Finance
Computational Geometry
Computational Topology
Computer Graphics and Computer Vision
Computer Systems
Cryptography and Security
Databases and Information Retrieval
Discrete Optimization
Discrete Probability
Distributed Algorithms
Experimental Algorithmics
Graph Drawing
Graphs and Networks
Machine Learning
Mathematical Programming
Molecular Computing
Number Theory and Algebra
On-line Problems
Pattern Matching and Data Compression
Quantum Computing
Random Structures
Robotics
Statistical Inference
Symbolic Computation

Deadline Dates

Submissions are due July 9, 2002 no later than 5:00 PM ET. Submissions received after this date will not be considered.

General Information

Registeration Information , Registration Form , Hotel Information , Hotel Form SOLD OUT, Transportation Information

How to Participate

PLEASE NOTE: The Procedures for electronic submission have changed.

To submit, visit http://cmt.research.microsoft.com/SODA03/CallForPapers.asp

Selection of Papers
The 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 especially 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, and 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 traditional extended abstracts and should report on original research that has not been published elsewhere, nor concurrently submitted to some other 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 types of papers in this category. Traditional SODA papers may be submitted under this category, but 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

Long Form Submissions:
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 achieved, 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. The entire extended abstract must not exceed 10 pages (using 11 point or larger font, with not less than one inch margins all around), including the bibliography and title page.

Short form Submissions:
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 achieved, 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 towards the specialist, can be provided as space permits. The entire short form abstract must not exceed 2 pages (using 11 point or larger font, with not less than one inch margins all around), including the bibliography and title page.

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

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

Paper Presenters
The Program Committee expects every speaker of a scheduled presentation to 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.


Conference 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 7, 2002; otherwise, the papers may not be included in the proceedings. The proceedings will be available at the Symposium.

Invited Speakers

Who Cares About Permanents?
Persi Diaconis, Stanford University

Data Streams: Algorithms and Applications
S. Muthukrishnan, Rutgers University and AT&T Shannon Labs

Browsing Around a Digital Library
Ian H. Witten, University of Waikato, New Zealand

Organizing Committee

Dimitris Achlioptas, Microsoft Research
Michael Bender, State University of New York, Stony Brook
Soumen Chakrabarti, IIT Bombay, India
Moses Charikar, Princeton University
Tamal Dey, Ohio State University
Jeff Erickson, University of Illinois, Urbana-Champaign
Martin Farach-Colton, (Chair) Rutgers University
Ron Graham, University of California, San Diego
Jerry Griggs, University of South Carolina
Claire Kenyon, Université Paris XI, France
Michael Krivelevich, Tel Aviv University, Israel
Stefano Leonardi, Università degli Studi di Roma "La Sapienza", Italy
Jiri Matousek, Univerzita Karlova v Praze, Czech Republic
Milena Mihail, Georgia Institute of Technology
Rajmohan Rajaraman, Northeastern University
R. Ravi, Carnegie Mellon University
Cenk Sahinalp, Case Western Reserve University
Raimund Seidel, Universität des Saarlandes, Germany
Eric Vigoda, University of Chicago
Gerhard Woeginger, University of Twente, Netherlands
Uri Zwick, Tel Aviv University, Israel

Program

Program Information will be available at this site soon.

Registration

Registeration Information , Registration Form , Hotel Information

Short Course

There are no Short Courses running in conjunction with this meeting.

Student Travel Awards

IBM Research Sponsors Student Travel Grants to SODA03

Award:
Ten awards of $500 each will be granted toward travel to SODA03.

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.


Deadlines:
Complete applications must be received at the SIAM office no later than Nov. 12, 2002.
Winner will be notified by December 6, 2002. 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.

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

SIAM
Attention: Joanna Littleton, IBM Research Student Travel Award, SODA 03
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.

SIAM Student Travel awards are also available. Please visit the HERE for further details.

Workshops

ALENEX'03

Algorithm Engineering and Experiments

On Saturday, January 11, 2003, the 5th Workshop on Algorithm Engineering and Experiments (ALENEX 03), will be held in Baltimore, Maryland at the Hyatt Regency Baltimore, on the Inner Harbour Hotel. It is co-located with the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA03), which will take place the following three days, January 12-14, 2003.

Richard Ladner, University of Washington, Program Chair

Steering Committee
Roberto Battiti, University of Trento, Italy
Adam Buchsbaum, AT&T Laboratories
Andrew Goldberg, Intertrust STAR Lab
Mike Goodrich, University of California, Irvine
David Johnson, AT&T Bell Laboratories
Catherine McGeoch, Amherst College
Bernard M.E. Moret, University of New Mexico
David Mount, University of Maryland
Jack Snoeyink, University of North Carolina, Chapel Hill
Cliff Stein, Columbia University

ALICE03

Algorithms for Listing, Counting and Enumeration

On Saturday, January 11, 2003, the 1st Workshop on Algorithms for Listing, Counting, and Enumeration (ALICE03), will be held in Baltimore, Maryland at the Hyatt Regency Baltimore, on the Inner Harbour Hotel. It will run concurrently with ALENEX (the 5th workshop on Algorithms Engineering and Experiments) and is co-located with the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA03), which will take place the following three days, January 12-14, 2003.

Invited speakers:

Robin Pemantle, Ohio State University
Carla Savage, North Carolina State University
Frank Ruskey, University of Victoria
Eric Vigoda, University of Chicago

Call for Participation:

We warmly invite submission of abstracts for those wishing to present a 25 minute talk at ALICE. ABSTRACTS SHOULD BE NO MORE THAN 2 PAGES WITH READABLE FONT AND REASONABLE MARGINS.

Abstracts should be submitted in text, Latex, postscript or pdf format by email to the program chair at [email protected] by September 20th. (If you submit an abstract, and do not recieve an email that says we could view and print your submission within 48 hours of submission, please email the program chair to verify your submission was recieved.)

Authors will be notified of acceptance by October 15th.

Program Committee:

Sylvie Corteel, Université de Versailles
Lenore Cowen, Tufts University (chair)
Martin Dyer, University of Leeds
Ira Gessel, Brandeis University
Leslie Goldberg, University of Warwick
Daniel Kleitman, Massachussetts Institute of Technology
Bob Robinson, University of Georgia
Herb Wilf, Univerity of Pennsylvania