Research News, December 2003


Previous News Next News

Return to Research News Index

These pages are edited by Philippe.Flajolet@inria.fr.

ANALCO'04 in New Orleans, January 10, 2004

The next coming event is ANALCO'04. This is the first edition of a one-day meeting collocated with SIAM SODA (the Symposium on Discrete Algorithms). This year, it will take place in New Orleans on January 10, 2003 in paralel with ALENEX'04. The complete programme is to be found at the SIAM site.

             

This one-day meeting is designed to offer a glimpse on current research in the area of Analysis of Algorithms. After a general presentation (by Sedgewick, I guess, as he has been the driving force behind the event), I will present some probabilistic counting algorithms. I don't have the promised survey written down at the moment, but let me just say that the problem addressed consists in estimating various characteristics of large volume of data. Such algorithms find use in data mining and monitoring routers activity, for instance. See on my web page the LogLog Counting algorithm developed with Marianne Durand, which is designed for estimating large (or huge) cardinalities using only a kilobyte or so of auxiliary memory. Wojtek Szpankowski and Mark Ward will present results on parameters of digital trees (aka tries) motivated by data compression and the celebrated Lempel-Ziv (LZ) algorithm: as many people know, the structure lurking behind LZ is a suffix tree, and suffix trees are a special brand of tries. Most probably, the Mellin transform should play a role in this, as well as in the papers by Helmut Prodinger and by Hitczenko-Knopfmacher. To fluctuate or not, that is the question...

Brigitte Vallée will present joint results obtained with Viviane Baladi that fully characterize in distribution the arithmetic complexity of Euclid's algorithm and its variants. A long version of their paper is now available under ArXiv. Constants related to such algorithms are hard to catch and Loick Lhote will present the first provably polynomial time algorithm for computing Wirsing's constant (giving the speed of convergence to the stationary regime), Hensley's constant (the variance coefficient),

H =  9.08037 31646 96850 36622 38092 15123 21337 99333 44476 ...
and many others. Martin Fürer will discuss a problem at the interface between numerical analysis and complexity theory, the title being "Quadratic Convergence for Scaling of Matrices".

Panario, Richmond, and Yip develop precise statistics on smallest prime factors of integers, a topic strongly tied to the analysis of simple integer factorization algorithms started by Knuth and Trabb Pardo some 25 years ago. Gill Barequet and Micha Moffie will discuss the complexity of a transfer matrix approach to counting self-avoiding polygons and walks exactly : thanks to such algorithms, we know for instance the exact number of closed self-avoiding walks in the plane till length 110, and from there a lot of precise facts can be distilled regarding the still mysterious self-avoiding walk: see Iwan Jensen's pages and the famous Encyclopedia of Integer Sequences for related data.

Conrado Martinez will conclude the day with detailed analyses and optimizations of partial quicksort, an algorithm designed to find the k smallest elements of an unsorted file by an elegant combination of QuickSort and Quickselect.

Other important 2004 events

More information will be given in later editions. Here are events that may primarily concern the AofA community.
    

10th International Workshop on Analysis of Algorithms June 14, 2004 to June 18, 2004

. In 2004, the annual AofA meeting will take place at Berkeley under the auspices of The Mathematical Research Institute, MSRI.

This event will be preceded by a two week course at MSRI, Berkeley: Analysis of Algorithms (Summer Graduate Program) June 2, 2004 to June 11, 2004 Organized by: P. Flajolet, G. Seroussi, W. Szpankowski, and M. Weinberger Please note, MSRI's Summer Graduate Programs are open only to students nominated by MSRI's Academic Sponsor universities. Here is the page at MSRI relative to this course.

    

Third Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities September 13-17, 2004, Vienna, Austria

. "These meetings aim at creating a forum for researchers working on the closely related domains of probabilities, trees, algorithms and combinatorics. Basic data structures of Computer Science, such as trees or graphs, can, and should, be studied from several points of view: as the data structure underlying some algorithms, or as a combinatorial or probabilistic object."

Regional 2004 events

    

ALEA'04

This meeting of the French ALEA Group will take place at Luminy near Marseilles. The CIRM Centre is already filled up with some 75 participants. There will be minicourses by Luc Devroye, Bernard Schmitt, and Gilles Schaeffer on random tree models, random texts and dynamical systems, and random maps, as well as some 25 presentations of recent research results.
  • Conference home page
  • List of participants.