Mathematical Sciences Research Institute

Home » Tenth Seminar on Analysis of Algorithms


Tenth Seminar on Analysis of Algorithms June 14, 2004 - June 18, 2004
Registration Deadline: May 23, 2004 over 18 years ago
To apply for Funding you must register by: March 14, 2004 almost 19 years ago
Parent Program: --
Organizers P. Flajolet, P. Jacquet, H. Prodinger, G. Seroussi, R. Sedgewick, W. Szpankowski, B. Vallée, and M. Weinberger

Show List of Speakers

The electronic journal Discrete Mathematics and Theoretical Computer Science defines the field of Analysis of Algorithms as follows: Analysis of algorithms is concerned with accurate estimates of complexity parameters of algorithms and aims at predicting the behavior of a given algorithm run in a given environment. It develops general methods for obtaining closed-form formulae, asymptotic estimates, and probability distributions for combinatorial or probabilistic quantities, that are of interest in the optimization of algorithms. Interest is also placed on the methods themselves, whether combinatorial, probabilistic, or analytic. Combinatorial and statistical properties of discrete structures (strings, trees, tries, dags, graphs, and so on) as well as mathematical objects (e.g., continued fractions, polynomials, operators) that are relevant to the design of efficient algorithms are investigated. Since its inception in 1963, the field has undergone substantial changes. We see now the emergence of combinatorial and asymptotic methods that allow the classification of data structures into broad categories that are amenable to a unified treatment. In recent years, probabilistic methods, which have been so successful in the study of random graphs and hard combinatorial optimization problems, have also been shown to play an important role in this field. These developments have two important consequences for the analysis of algorithms: it becomes possible to predict average behavior under more general probabilistic models than before; at the same time it becomes possible to analyze algorithms that are more structurally complex than before. To achieve these goals, the analysis of algorithms draws on a number of branches of mathematics: combinatorics, probability theory, graph theory, real and complex analysis, number theory, and occasionally algebra, geometry, operations research, and others. Information theory appears to be an area of strong synergy with analysis of algorithms. This synergy has already yielded very interesting results, such as the characterization of structural properties of the Lempel-Ziv parsing tree and a precise asymptotic characterization of the redundancy of the Lempel-Ziv data compression scheme. Thus, techniques from analysis of algorithms have given new insights into the structure of the algorithms used in information theory, as well as their information-theoretic performance. One of the goals of this workshop will be to explore this inter-disciplinary connection further. We anticipate that the workshop will include about 30 lectures and 5 plenary speakers.
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Funding & Logistics Show All Collapse

Show Funding

To apply for funding, you must register by the funding application deadline displayed above.

Students, recent Ph.D.'s, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available.

Show Lodging

MSRI does not hire an outside company to make hotel reservations for our workshop participants, or share the names and email addresses of our participants with an outside party. If you are contacted by a business that claims to represent MSRI and offers to book a hotel room for you, it is likely a scam. Please do not accept their services.

MSRI has preferred rates at the Hotel Shattuck Plaza, depending on room availability. Guests can call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Institute discount. To book online visit this page (the MSRI rate will automatically be applied).

MSRI has preferred rates at the Graduate Berkeley, depending on room availability. Reservations may be made by calling 510-845-8981. When making reservations, guests must request the MSRI preferred rate. Enter in the Promo Code MSRI123 (this code is not case sensitive).

MSRI has preferred rates at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select "Affiliated with the Space Sciences Lab, Lawrence Hall of Science or MSRI." When prompted for your UC Contact/Host, please list Chris Marshall (coord@msri.org).

MSRI has a preferred rates at Easton Hall and Gibbs Hall, depending on room availability. Guests can call the Reservations line at 510-204-0732 and ask for the MSRI- Mathematical Science Research Inst. rate. To book online visit this page, select "Request a Reservation" choose the dates you would like to stay and enter the code MSRI (this code is not case sensitive).

Additional lodging options may be found on our short term housing page.

Show Directions to Venue

Show Visa/Immigration