Research News, November 2004

Previous News Next News

Return to Research News Index

Issue dated November 11, 2004

• ANALCO'05 in Vancouver (January 2005)
• AofA'05 in Barcelona (June 2005). algorithms.
• Special Issue on Analysis of Algorithms in Algorithmica, deadline January 15, 2005.

ANALCO'05

This is a one day meeting with refereed communications.

The aim of the ANALCO workshop is to provide a forum for the presentation of original research in the analysis of algorithms and associated combinatorial structures. We invite both papers that study properties of fundamental combinatorial structures that arise in practical computational applications (such as permutations, trees, strings, tries, and graphs) and papers that address the precise analysis of algorithms for processing such structures. This includes average-case analysis; analysis of moments, extrema, and distributions; and probabilistic analysis of randomized algorithms. Submissions that present significant new information about classic algorithms are welcome, as are analyses of new algorithms that present unique analytic challenges. We also invite submissions that address tools and techniques for the analysis of algorithms and combinatorial structures, both mathematical and computational. The scientific program will include invited talks, contributed research papers, and ample time for discussion and debate of topics in this area. The programme is accessible here.

9:00 AM Analytic Algorithmics, Combinatorics, and Information Theory
Invited Speaker: Wojciech Szpankowski, Purdue University

10:30 AM Performance Evaluation of Demodulation with Diversity---A Combinatorial Approach III
Simon Bliudze and Daniel Krob, Ecole Polytechnique, France

11:00 AM Comparison of Two CDS Algorithms on Random Unit Ball Graphs
Jennie Hansen, Herriot-Watt University, United Kingdom, and Eric Schmutz, Drexel University

11:30 AM Complexity of the Path multi-peg Tower of Hanoi
Daniel Berend and Amir Sapir, Ben-Gurion University, Israel

1:30 PM Mixing Points on an Interval
Dana Randall, Georgia Institute of Technology, and Peter Winkler, Dartmouth University

2:00 PM Enumeration of Binary Trees, Lempel-Ziv’78 Parsings, and Universal Types
Charles Knessl, University of Illinois, Chicago, and Wojciech Szpankowski, Purdue University

2:30 PM On the Average Density and Selectivity of Nodes in Multi-Digit Tries
Yuriy Reznik, RealNetworks

3:00 PM Coffee Break (Junior Ballroom C&D)

3:30 PM Mixing Times for Random Walks on Geometric Random Graphs
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavret Shah, Stanford University

4:00 PM Counting Structures in Grid Graphs, Cylinders and Tori Using Transfer Matrices
Mordecai Golin, Yiu Leung, Yajun Wang, Xuerong Yong, Hong Kong and DIMACS

4:30 PM Counting Eulerian Circuits is #P-Complete
Graham Brightwell, London School of Economics, and Peter Winkler, Dartmouth University

5:00 PM Approximately Counting Perfect Matchings in General Graphs
Martin Furer and Shiva Kasiviswanathan, Pennsylvania State University

      

AofA 2005.

The 2005 Conference on Analysis of Algorithms (AofA'05), will be held in Barcelona on June 6-10, 2005.

From the Call for Papers [PDF], we find:

"Predicting the performance of algorithms is a likely outgrowth of ongoing research in analytic combinatorics and the analysis of random discrete structures. This workshop will bring together leading researchers in this field to focus on such problems. [...]
The focus of this workshop is the average case analysis of algorithms, and its relation to the wider areas of analytic combinatorics, exact and limiting distributions, formal techniques, probability theory, combinatorics and computer science. We identify the following areas as being of particular interest:
• Properties of large randomly formed data structures.
• Analytic tools for analysis of algorithms.
• Probabilistic methods for analysis of algorithms.
• Combinatorial methods for analysis of algorithms.
• New results concerning average case analysis of classical or new algorithms.
• Data compression and language-modeling methods."

IMPORTANT DATES

• February 25, 2005: deadline for submissions.
• March 31, 2005: Notification
• June 6-10: AofA'05 in Barcelona

This first conference on Analysis of Algorithms takes place after a series of ten highly successful international workshops intended to bring together researchers working in this area. The previous meetings were held in Schloss Dagstuhl, Germany in 1993, 1995, and 1997, Princeton, USA (1998), Barcelona, Spain (1999), Krynica Morska, Poland (2000), Tatihou, France (2001), Strobl, Austria (2002), San Miniato, Italy (2003) and Berkeley, USA (2004).

Following the tradition of the ten previous seminars, this Conference intends to bring together leading researchers in the Analysis of Algorithms and provide them with a relaxed atmosphere for interaction and discussion. Therefore, the talks will generally be brief and somewhat sparse. Long lunch breaks and one free afternoon will be purposely planned. A problem session will also be organized.

The chair is Conrado Martínez

Special Issue of Algorithmica on AofA

"Average-Case Analysis of Algorithms is the area of Theoretical Computer Science that studies the behavior of algorithms on random inputs. The focus is on average-case analysis of algorithms, deviations from the mean, probability properties that explain the behavior of algorithms on random inputs, among others. The area was initiated by D. E. Knuth more than 40 years ago in order to understand the behavior of algorithms from a quantitative point of view. Performance evaluation of algorithms has been recently the subject of renewed interest. This is due, in part, to the increasing importance of randomized algorithms, and also to the explosion of the digital world, in which inputs are so large that they can only be described in a probabilistic manner.

There have been many new developments in the area of analysis of algorithms in recent years, either due to novel applications (e.g., dynamic data structures, information theory) or due to new methodological tools (e.g., symbolic computation, new methods for asymptotic analysis, new probabilistic techniques). The problems are both practically interesting and mathematically challenging; the new tools are highly nontrivial.

This special issue is seeking papers in any area of theoretical computer science that uses analytical, probabilistic or combinatorial methods to derive average-case analysis of algorithms. To mention a few: sorting and searching, discrete and combinatorial optimization, arithmetic algorithms, algorithms on graphs, coding and communications, algorithms on strings including those applied to molecular biology and data compression, etc. Papers that present new methodological approaches or that deal with random combinatorial structures will also be considered.

A series of seminars dedicated to the the analysis of algorithms was started on 1993. The latest of these seminars was held at the Mathematical Sciences Research Institute (MSRI, Berkeley); see http://www.cs.purdue.edu/homes/spa/aofa04.html. A special issue of Algorithmica is planned for 2005 on the average case analysis of algorithms to summarize recent achievements in the area. The guest editors: Philippe Jacquet (INRIA, France), Daniel Panario (Carleton, Canada) and Wojciech Szpankowski (Purdue, USA) invite you to submit a paper. Prospective authors should follow the regular guidelines of the journal except that they should send electronically a postscript or pdf file to either Philippe Jacquet (philippe.jacquet@inria.fr) or Daniel Panario (daniel@math.carleton.ca). The deadline for submission is December 15, 2004."

Guest Editors Philippe Jacquet, Daniel Panario, Wojciech Szpankowski.
(INRIA Rocquencourt; School of Math., Carleton University, Ottawa; Stat. Dept. of Computer Science Rocqunecourt Carleton University, Purdue University)
philippe.jacquet AT inria.fr; daniel AT math.carleton.ca; spa AT cs.purdue.edu.

         

(Last updated, November 12, 2004)

To be continued...