Volumes

DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (35 articles)

The present volume collects the proceedings of the Aofa'12, 23st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms held at the Centre de Recherches Mathématiques at Université de Montreal, Canada, between June 18-22, 2012. The conference builds on the communities of the former series of conferences ``Mathematics and Computer Science'' and ``Analysis of Algorithms'', and aims at studying rigorously the combinatorial objects which appear in particular as data structures, algorithms, models of networks and as well as the essential ubiquitous combinatorial structures. The program committee selected submissions covering this wide range of topics. The regular papers were presented in 30-minute talks, and short abstracts in presentations of 15 minutes. They all appear in the present volume.

 

The conference included five invited plenary lectures:

  • Michael Drmota (TU Vienna, Austria): Extremal parameters in critical and subcritical graph classes
  • Svante Janson (Uppsala, Sweden): Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
  • Amin Coja-Oghlan (Warwick, UK): Phase transitions and computational complexity
  • Claire Mathieu (Brown, USA): Algorithms for optimization over noisy data
  • Avi Wigderson (IAS, USA): Population Recovery via Partial Identification

We thank the members of the steering and program committees for their involvement. We also thank the invited speakers, and the authors of the contributed papers. We express our gratitute to the people at CRM and especially Louis Pelletier for their invaluable help in making sure that the meeting went smoothly. We are also grateful to the editor-in-chief of DMTCS Jens Gustedt for his help in the compilation of the proceedings.

Finally, our special thanks go to the sponsors of the conference for their contributions: CRM, Inria, and NSERC.

Nicolas Broutin and Luc Devroye, Editors

 

Steering Committee

  • Brigitte Chauvin (Versailles, France)
  • Luc Devroye (McGill, Canada)
  • Michael Drmota (TU Vienna, Austria)
  • Daniel Panario (Carleton, Canada)
  • Robert Sedgewick (Princeton, USA)
  • Wojciech Szpankowski (Purdue, USA)
  • Brigitte Vallée (Caen, France)

 

Program Committee

  • Frédérique Bassino, Paris 13, France
  • Jit Bose, Carleton, Canada
  • Nicolas Broutin (co-chair), Inria, France
  • Philippe Chassaing, Nancy, France
  • Julien Clément, Caen, France
  • Luc Devroye (co-chair), McGill, Canada
  • Uriel Feige, Weizmann, Israel
  • Alan Frieze, Carnegie-Mellon, USA
  • Bernhard Gittenberger, TU Vienna, Austria
  • Hsien-Kuei Hwang, Academia Sinica, Taiwan
  • Philippe Jacquet, Inria, France
  • Colin McDiarmid, Oxford, UK
  • Mike Molloy, Toronto, Canada
  • Ralph Neininger, Frankfurt, Germany
  • Marc Noy, Barcelona, Spain
  • Daniel Panario, Carleton, Canada
  • Alois Panholzer, TU Vienna, Austria
  • Bruno Salvy, Inria, France
  • Mohit Singh, McGill, Canada
  • Brigitte Vallée, Caen, France
  • Mark Ward, Purdue, USA
 
Organization
  • Nicolas Broutin
  • Luc Devroye


DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems (11 articles)

This volume contains all the full papers presented at AUTOMATA 2011, the 17th international workshop on cellular automata and discrete complex systems. The workshop was held on November 21-23, 2011, at the Center for Mathematical Modeling, University of Chile, Santiago, Chile.

AUTOMATA is an annual workshop on the fundamental aspects of cellular automata and related discrete dynamical systems. The spirit of the workshop is to foster collaborations and exchanges between researchers on these areas. The workshop series was started in 1995 by members of the Working Group 1.5 of IFIP, the International Federation for Information Processing.

The volume contains the « full » papers selected by the program committee, which consisted of 27 international experts on cellular automata and related models, and the selection was based on 3 peer reviews on each paper.

Papers in this volume represent a rich sample of current research topics on cellular automata and related models. The papers include theoretical studies of the classical cellular automata model, but also many investigations into various variants and generalizations of the basic concept. The versatile nature and the flexibility of the model is evident from the presented papers, making it a rich source of new research problems for scientists representing a variety of disciplines.

As the editors of these proceedings, we thank all contributors to the scientific program of the workshop. We are especially indebted to the invited speakers and the authors of the contributed papers.

Nazim Fatès, Eric Goles, Alejandro Maass, Iván Rapaport


Program Committee

  • Andrew Adamatzky, University of West England, UK
  • Stefania Bandini, Università degli Studi di Milano-Bicocca, Italy
  • Marie-Pierre Béal, Université Paris-Est, France
  • Bruno Durand, Université de Provence, France
  • Nazim Fatès, Inria Nancy Grand-Est, France, co-chair
  • Paola Flocchini, University of Ottawa, Canada
  • Enrico Formenti, Université de Nice-Sophia Antipolis, France
  • Henryk Fuks, Brock University, Canada
  • Anahí Gajardo, Universidad de Concepción, Chile
  • Eric Goles, Universidad Adolfo Ibáñez, Chile, co-chair
  • Martin Kutrib, University of Giessen, Germany
  • Alejandro Maass, Universidad de Chile, co-chair
  • Andrés Moreira, Universidad Técnica Federico Santa María, Chile
  • Kenichi Morita, Hiroshima University, Japan
  • Pedro de Oliveira, Universidade Presbiteriana Mackenzie, Brazil
  • Nicolas Ollinger, Université de Provence, France
  • Ronnie Pavlov, Denver University, USA
  • Marcus Pivato, Trent University, Canada
  • Ivan Rapaport, Universidad de Chile, co-chair
  • Dipanwita Roychowdhury, Indian Institute of Technology, India
  • Mathieu Sablik, Université de Provence
  • Michael Schraudner, Universidad de Chile
  • Klaus Sutner, Carnegie Mellon, USA
  • Guillaume Theyssier, CNRS, Université de Savoie, France
  • Edgardo Ugalde, Universidad Autónoma de San Luis Potosí, Mexico
  • Hiroshi Umeo, Osaka Electro-Communication University, Japan
  • Thomas Worsch, Karlsruhe University, Germany


DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) (81 articles)


DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) (82 articles)

We were very pleased to receive a record number of submissions this year covering the spectrum of combinatorics and its applications. The presentations will cover many exciting new results and build connections between research areas. We hope you will be able to attend all the lectures and the two poster sessions. We encourage you to ask questions, discuss the material during breaks and participate fully in the FPSAC experience.

Our thanks goes out to everyone attending FPSAC 2010, and especially the members of the Program and Organizing Committees. We also thank the following organizations for their financial support: the National Science Foundation, the National Security Agency, the San Francisco State University College of Science and Engineering and Department of Mathematics, the Fields Institute, Elsevier, and Lindo Systems. Finally, we hope everyone will join us in thanking Federico Ardila and Matthias Beck for taking on the huge job of co-chairing the Organizing Committee.

Sara Billey & Vic Reiner

Program Committee co-chairs

 

Program committee
  • Sara Billey (University of Washington, USA, co-chair)
  • Vic Reiner (University of Minnesota, USA, co-chair)
  • Michael Albert (University of Otago, New Zealand)
  • Francesco Brenti (Universita' di Roma "Tor Vergata", Italy)
  • Sylvie Corteel (Université Paris XI, France)
  • Sergi Elizalde (Dartmouth College, USA)
  • Dmitry Feichtner-Kozlov (Universität Bremen, Germany)
  • Ira Gessel (Brandeis University, USA)
  • Curtis Greene (Haverford College, USA)
  • Jim Haglund (University of Pennsilvania, USA)
  • Sam Hsiao (Bard College, USA)
  • Jakob Jonsson (KTH, Sweden)
  • Gil Kalai (Hebrew University, Israel)
  • Carly Klivans (University of Chicago, USA)
  • Fu Liu (University of California, Davis, USA)
  • Soichi Okada (Nagoya University, Japan)
  • Julian Pfeifle (Universitat Politècnica de Catalunya, Spain)
  • Alexander Postnikov (Massachusetts Institute of Technology, USA)
  • David Speyer (Massachusetts Institute of Technology, USA)
  • Volkmar Welker (Philipps-Universität Marburg, Germany)
  • Alex Yong (University of Illinois at Urbana-Champaign, USA)
  • Mike Zabrocki (York University, Canada)
 
Organization committee
  • Federico Ardila (San Francisco State University, USA, co-chair)
  • Matthias Beck (San Francisco State University, USA, co-chair)
  • Nantel Bergeron (York University, Canada)
  • Thomas Bliem (San Francisco State University, USA and Universität zu Köln, Germany)
  • Tristram Bogart (San Francisco State University, USA and Queen's University, Canada)
  • Serkan Hosten (San Francisco State University, USA)
  • Brant Jones (University of California, Davis, USA)
  • Fu Liu (University of California, Davis, USA)
  • Peter McNamara (Bucknell University, USA)
  • Ellen Veomett (California State University, East Bay, USA)
  • Mike Zabrocki (York University, Canada)


DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (41 articles)

This Proceedings volume is devoted to the Aofa'10, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms, which was held at the Vienna University of Technology, Austria, during June 28 - July 2, 2010. This conference is the first joint meeting of two previous conference and seminar series on ``Mathematics and Computer Science'' and ``Analysis of Algorithms''. The common aim of these and the present meeting is to study discrete objects that appear as data structures or algorithms (including graphs, networks etc.) by mathematical methods, in particular by probabilistic, combinatorial and asymptotic methods. However, the topics of the conference are meant in a broad sense and so the programme committee selected 41 papers covering a wide range of fields. The 41 papers were presented in 30 minutes talks and all of them appear in this DMTCS Proceedings volume.

The programme of the conference was complemented by the following five 60 minutes invited lectures:

Noga Alon (Tel Aviv University, Israel)Color Coding: Variations and Applications
Yuliy Baryshnikov (Bell Laboratories, USA)Search on the Brink of Chaos
Daniel Panario (Carleton University, Canada)Polynomials over Finite Fields: Algorithms and Randomness
Oliver Riordan (University of Oxford, England)Percolation on Graphs
Peter Winkler (Dartmouth, USA)The Automaton as Statistician

Before the conference a Mini-Summerschool with lectures by Nicolas Broutin (INRIA Rocquencourt), Christian Krattenthaler (Univ. Wien), Angelika Steger (ETH Züurich), and Wojciech Szpankowski (Purdue Univ.) took place during June 25-26, 2010.

Furthermore a poster session was organized with posters presented by Zareen Alamgir, Saira Karim, and Syed Husnine; Milan Bradonjic, Aric Hagberg, Nick Hengartner and Allon G. Percus; Boris Granovsky; Immanuel Halupczok and Jan-Christoph Schlage-Puchta; Madhu Jain and G.C. Sharma; Daniel Krenn; Manfred Madritsch; Dimbinaina Ralaivaosaona; Alexey Ustinov; Martin Zeiner.

We express our gratitude to the members of the Programme Committee for their careful selection of the 41 contributed papers. This eventually guaranteed the high quality and the wide range of topics of the conference. We thank the members Steering Committee and the members of the Organisation Committee for the organizational work. Furthermore, we thank all the invited speakers, the authors of papers or posters, and all the participants of the conference. We are also grateful to the editor-in-chief of DMTCS Jens Gustedt and to Cyril Banderier for technical assistance during the compilation of the proceedings.

Last but not least we express our special thanks to the Austrian Science Foundation FWF, the City of Vienna as well as the Vienna University of Technology for the financial support of the conference.

Michael Drmota and Bernhard Gittenberger
Editors


Steering Committee
Brigitte Chauvin, Versailles (France)
Luc Devroye, Montreal (Canada)
Michael Drmota, Vienna (Austria)
Philippe Flajolet, INRIA Rocquencout (France)
Robert Sedgewick, Princeton (USA)
Wojciech Szpankowski, Purdue (USA)

Programme committee
Chair: M. Drmota, Vienna (Austria)
B. Chauvin, Versailles (France)
Jacek Cichon, Wroclaw (Poland)
Philippe Flajolet; INRIA Rocquencourt (France)
Daniele Gardy, Versailles (France)
Martin Klazar, Prague (Czech Republic)
J.-F. Legall, Paris (France)
Conrado Martinez, Barcelona (Spain)
Ralph Neininger, Frankfurt (Germany)
Marc Noy, Barcelona (Spain)
Alois Panholzer, Vienna (Austria)
Helmut Prodinger, Stellenbosch (South Africa)
Uwe Roesler, Kiel (Germany)
Bob Sedgewick, Princeton (USA)
Wojciech Szpankowski, Purdue (USA)
Peter Winkler, Dartmouth (USA)

Organisation Committee
Chair: Bernhard Gittenberger
Michael Drmota
Alois Panholzer


DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS (9 articles)

This volume contains the selected "full" papers presented at AUTOMATA 2010, the 16th inter- national workshop on cellular automata and discrete complex systems. The workshop was held on June 14-16, 2010, at the LORIA laboratory in Nancy, France. AUTOMATA is an annual workshop on the fundamental aspects of cellular automata and related discrete dynamical sys- tems. The spirit of the workshop is to foster collaborations and exchanges between researchers on these areas. The workshop series was started in 1995 by members of the Working Group 1.5 of IFIP, the International Federation for Information Processing. The program committee consisted of 25 international experts on cellular automata and related models, and the selection was based on 2-4 peer reviews on each paper. Papers in this volume represent a rich sample of current research topics on cellular automata and related models. The papers include theoretical studies of the classical cellular automata model, but also many investigations into various variants and generalizations of the basic concept. The versatile nature and the flexibility of the model is evident from the presented papers, making it a rich source of new research problems for scientists representing a variety of disciplines.

As the editors of these proceedings, we thank all contributors to the scientific program of the workshop. We are especially indebted to the invited speakers and the authors of the contributed papers. We would also like to thank the members of the Program Committee and the external reviewers of the papers.

Nazim Fatès, Jarkko Kari, Thomas Worsch


DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (77 articles)

FPSAC 2009 was held at the Research Institute for Symbolic Computation, Hagenberg, Austria, on July 20-24, 2009.
Editors:
Christian Krattenthaler, Volker Strehl, and Manuel Kauers

Preface

This Proceedings volume is devoted to the 21st International Conference on Formal Power Series and Algebraic Combinatorics, held at the Research Institute of Symbolic Computation (RISC) in Hagenberg, Austria, during 20-24 July 2009. The conference was extremely well attended: 200 graduate students, junior researchers, and senior researchers from Austria, Canada, Colombia, China, Czech Republic, Denmark, France, Germany, Greece, Iceland, Israel, Italy, Japan, Mexico, Poland, Portugal, Slovenia, Spain, South Africa, South Korea, Sweden, the United Kingdom, and the United States gathered to enjoy the overwhelming hospitality of the RISC Combinatorics Group.

The conference programme featured nine invited lectures, given by Alexander Barvinok, Karin Erdmann, Jaroslav Nesetril, Bruno Salvy, Carsten Schneider, Michael Singer, Frank Sottile, Volkmar Welker, and Ae Ja Yee, 26 contributed talks, and 48 poster presentations. This volume contains the extended abstracts for most of the contributed papers and poster presentations, all of which had been selected in a careful reviewing process by the programme committee from submissions. These extended abstracts show the wide range of topics presented at the conference, linked together by the overall theme of Formal Power Series and Algebraic Combinatorics. These included enumeration, combinatorial geometry, commutative algebra, algebraic geometry, combinatorial representation theory, Hopf algebras, computational complexity, algebraic graph theory, and, of course (genius loci!), computer algebra. We thank all contributors and participants for having made this conference a show-case of current trends in the field and a lively place of exchange of ideas.

The organizers are very grateful for the financial support of the Johannes Kepler University Linz, the Austrian Science Foundation FWF, the province of Upper Austria, the University Fund Linz (Linzer Hochschulfonds), the Austrian Ministry of Science, the US National Science Foundation (NSF), and the US National Security Agency (NSA). They made it possible, with Susanna Fishel as manager, that a large number of young researchers could profit from this conference, respectively present their work. Funds generously provided by Elsevier were allocated to the Elsevier award for best extended abstract by a student (Guillaume Chapuy).

We would like to thank all of those who served on the Programme and Organising Committees, without whose contribution such a conference could never have been held. Furthermore, the help of Tanja Gutenbrunner, Gabriela Hahn, Veronika Pillwein, Marion Schimpl, and Ralf Hemmecke was more than invaluable to the local organizers.

Manuel Kauers (Scientific Programme Manager)
Christian Krattenthaler (Co-chair, Programme Committee)
Peter Paule (Chair, Organising Committee)
Volker Strehl (Co-chair, Programme Committee)

Committees
Program Committee

  • Christian Krattenthaler (Co-Chair; University of Vienna, Austria)
  • Volker Strehl (Co-Chair; University of Erlangen, Germany)
  • Matthias Beck (San Francisco State University, USA)
  • Philippe Caldero (Universite Lyon-I, France)
  • Eva-Maria Feichtner (University of Bremen, Germany)
  • Sergey Fomin (University of Michigan, USA)
  • Jan de Gier (University of Melbourne, Australia)
  • Antonio Giambruno (University of Palermo, Italy)
  • Takayuki Hibi (University of Osaka, Japan)
  • Alain Lascoux (Universite Marne-la-Vallee, France)
  • Ezra Miller (University of Minnesota, Minneapolis, USA)
  • Maxim Nazarov (University of York, UK)
  • Marc Noy (Univ. Politecnica de Catalunya, Barcelona, Spain)
  • Grigori Olshanski (Dobrushin Mathematics Laboratory, Moscow, Russia)
  • Soichi Okada (University of Nagoya, Japan)
  • Marko Petkovsek (University of Ljubljana, Slovenia)
  • Amitai Regev (Weizmann Institute, Rehovot, Israel)
  • Monica Vazirani (University of California, Davis, USA)
  • Michelle Wachs (University of Miami, USA)
  • Lauren K. Williams (Harvard University, Boston, USA)
  • Catherine Yan (Texas A&M University, USA)

Organizing Committee

  • Peter Paule (Chair; RISC, Johannes Kepler University Linz, Austria)
  • Susanna Fishel (Arizona State University, USA)
  • Ralf Hemmecke (RISC, Johannes Kepler University Linz, Austria)
  • Manuel Kauers (RISC, Johannes Kepler University Linz, Austria)
  • Franz Lichtenberger (RISC, Johannes Kepler University Linz, Austria)
  • Wolfgang Windsteiger (RISC, Johannes Kepler University Linz, Austria)

Local Arrangements Committee

  • Veronika Pillwein (Chair; DK Computational Math., Johannes Kepler University Linz, Austria)
  • Burcin Erocal (RISC, Johannes Kepler University Linz, Austria)
  • Christoph Koutschan (RISC, Johannes Kepler University Linz, Austria)
  • Clemens Raab (DK Computational Mathematics, Johannes Kepler University Linz, Austria)
  • Silviu Radu (RISC, Johannes Kepler University Linz, Austria)
  • Flavia Stan (RISC, Johannes Kepler University Linz, Austria)


DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) (61 articles)

Programme Committee-Comité de Programme
 
Bruce Sagan (Michigan State University, USA) (Chair)
Christian Krattenthaler (Universität Wien, Austria) (Co-chair)
Federico Ardila (San Francisco State University, USA)
Jean-Christophe Aval (Université Bordeaux 1, France)
Christine Bessenrodt (Universität Hannover, Germany)
Xun Dong (University of Miami, USA)
Susanna Fishel (Arizona State University, USA)
Sergey Fomin (University of Michigan, USA)
Patricia Hersh (Indiana University, USA)
Ronald King (University of Southampton, UK)
Luc Lapointe (Universidad de Talca, Chile)
Jeremy Lovejoy (Université Denis Diderot, France)
Jeremy Martin (University of Kansas, USA)
Jean-Christophe Novelli (Université de Marne-la-Vallée, France)
Frédéric Patras (Université de Nice, France)
Peter Paule (Universität Linz, Austria)
Nathan Reading (North Carolina State University, USA)
Bruno Salvy (INRIA, France)
Mark Shimozono (Virginia Tech University, USA)
Einar Steingrímsson (Reykjavik University, Iceland)
Itaru Terada (University of Tokyo, Japan) Organizing Committee-Comité d'Organisation Federico Ardila (San Francisco State University, USA)
Hélène Barcelo (Arizona State University, USA)
Christian Krattenthaler (Universität Wien, Austria)
María Ines Icaza (Universidad de Talca, Chile)
Luc Lapointe (Universidad de Talca, Chile) (Chair)
Jennifer Morse (Drexel University, USA)
 
Foreword
 

This Proceedings volume is devoted to the 20th International Conference on Formal Power Series and Algebraic Combinatorics, held in Viña del Mar, Chile, during 23-27 June 2008. The conference attracted an audience of approximately 120 participants, consisting of graduate students, junior researchers, and senior researchers from Argentina, Australia, Austria, Canada, Chile, Colombia, China, France, Germany, Iceland, Israel, Japan, South Korea, Mexico, New Zealand, Portugal, Russia, Spain, Sweden, the United States and Venezuela.

The conference was dedicated to Pierre Leroux (1942-2008), who, while serving as president of the permanent programme committee of this conference series from 1991 to 1998, has been one of the driving forces which have made this series into the continuing success that it has been over the past 20 years.

The conference programme featured eight invited lectures, given by Marcelo Aguiar, Michael Albert, Jonathan Brundan, Dmitry Feichtner-Kozlov, Gilbert Labelle, Alexander Postnikov, María Ronco, and Carla Savage, 26 contributed talks, and 39 poster presentations. This volume contains the extended abstracts for most of the contributed talks and poster presentations, all of which had been selected in a careful reviewing process by the programme committee from submissions. These extended abstracts reflect the thematic breadth of the conference by covering aspects of Formal Power Series and Algebraic Combinatorics, including enumeration, commutative algebra, algebraic geometry, combinatorial representation theory, Hecke algebras, Hopf algebras, computational complexity, and statistical physics. We thank all contributors and participants for having made this conference a show-case of current trends in the field and a lively place of exchange of ideas.

The organizers are very grateful for the financial support of the Universidad de Talca (through funds from the Dirección de Investigación y Asistencia Técnica and the Instituto de Matemáticas) and of the Programa Bicentenario de Ciencia y Tecnología: Anillo Ecuaciones Asociadas a Reticulados (Chile). Many American participants were given the opportunity to attend the conference thanks to the support of the National Science Foundation and the National Security Agency. The Fields Institute was very helpful in managing the registration process, and funds generously provided by Elsevier were allocated to the Elsevier award for best extended abstract by a student (Valentin Féray) and to the support of Latin American participants.

We would like to thank all of those who served on the Programme and Organizing Committees, whitout whose contribution such a conference could never have been held. Finally, the help of Ricardo Baeza, Andrés Bustamante, Erdal Emsiz, Raimundo Hamilton, Ana Cecilia de la Maza, María Elena Pinto, Nancy Ruminot, Steen Ryom-Hansen, and especially Blanca Zúñiga, was more than invaluable to the local organizers.

Christian Krattenthaler
Luc Lapointe
Bruce Sagan


DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (38 articles)

The Fifth Colloquium on Mathematics and Computer Science is, singularly, the sixth one in a series of events that began at the University of Versailles Saint-Quentin with the Colloque Arbres in June 1995, then went on to the First and Second Colloquia on Mathematics and Computer Science in September 2000 and 2002, again in Versailles, the third edition being hold in Vienna in 2004 and the fourth in Nacy 2006. These meetings aim try provide 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.

The previous meetings were very well received and established a vivid and increasing cooperation between mathematicians and researchers in computer science. Both communities get their reward from the cooperation. For mathematicians computer science is a rich source of interesting and new structures, which require a systematic approach and provide new insights. For theoretical computer science researcher it is a source of mathematical knowledge and a platform for exchanging problems and for abstract research on theoretical fundamentals. The previous meetings as well as this one showed an ongoing research and an development of new tools and methods, like in probability, combinatorics and singularity analysis. In this sense, the meetings serves as a melting pot for different views, attitudes and cultures.

With the organization of the 2008 Colloquium, we hope to have contributed further progress on topics at the boundary (or closed partly the gap) between probability theory and theoretical computer science. Papers were sought in a wide spectrum of mathematical areas, for instance random trees, stochastic processes, large deviations, branching processes, random walks, discrete probabilities, analytical and enumerative combinatorics, run time analysis of algorithms and data structures, performance evaluation, random generation of combinatorial structures, singularity analysis, logic, number theory, statistics, stochastic geometry and so on. A large Program Committee, guaranteeing wide coverage of subtopics and expertise in a variety of fields, selected 34 papers for a presentation as 30-minute talks and some for a presentation as a poster. Almost all talk presentations appear in this volume of the journal Discrete Mathematics & Theoretical Computer Science. Furthermore, eight one-hour plenary lectures were presented by the following invited speakers (appearing in alphabetical order)

Philippe Chassaing (Université Henri Poincaré, France)
Jean-Francois Le Gall (Université Paris-Sud, France)
Malwina Luczak (The London School of Economics and Political Sience, Great Britain)
Ralph Neininger (Johann Wolfgang Goethe Universität, Germany)
Mathew Penrose (University of Bath, England)
Angelika Steger (ETH Zürich, Switzerland)
Wojciech Szpankowski (Purdue University, USA)
Joseph E. Yukich (Lehigh University, USA).

The papers assembled in this volume offer snapshots of current research. Moreover, some of them, in particular invited talks, include carefully crafted surveys of their field. The variety of topics illustrate the numerous ramifications of the theory of discrete and random discrete structures throughout mathematics and computer science. And they show the interplay of different fields.

I wish to express my gratitude and indebtness to the members of the Program Committee, who I was honoured to chair, to the members of the Organizing Committee, to the invited speakers and to all the authors and participants of the conference contributing to the great success of the conference. Thanks for all the constructive support, fast reports of the referees, sound advice by the organizing committee, help of the editor-in-chief of DMTCS and many more. Especially I like to thank the coorganizers of the meeting, Rudolph Grübel and Ludger Rueschendorf, for sharing the work, Jan Spitzman for his internet support and the edition of this volume, our secretary Mrs. Ceuleman for the autonomous work and Mrs. Riemer at the desk office.

Last but not least, I would like to thank for financial support by the DFG and the Center of Scientific Computing (CSC) in Kiel. Further the Christian-Albrechts-Universität zu Kiel provided substantial help in many respects.

Kiel, September 2008
Uwe Roesler
Chair of the Program Committee

Program Committee

Philippe Chassaing (Université Henri Poincaré, France)
Brigitte Chauvin (Université de Versailles, France)
Michael Drmota (Technische Universität Wien, Austria)
Philippe Flajolet, (INRIA, France)
Danièle Gardy (Université de Versailles, France)
Rudolf Grübel (Leibniz Universität Hannover, Germany)
Uwe Roesler, chair, (Christian-Albrechts-Universität Kiel, Germany)
Ludger Rüschendorf (Albert-Ludwigs-Universität Freiburg, Germany)
Gilles Schaeffer (CNRS, France)
Robert Sedgewick (Princeton University, USA)
Wojciech Szpankowski (Purdue University, USA)
Brigitte Vallée (Université de Caen, France)


DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (36 articles)

The 2007 Conference on Analysis of Algorithms (AofA'07), has been held in Juan des Pins near the cities of Antibes and Nice, France, on June 17-22, 2007.

The Analysis of Algorithms is a scientific basis for computation, providing a link between abstract algorithms and the performance characteristics of their implementations in the real world. The general effort to precisely predict the performance of algorithms has come to involve research in analytic combinatorics, the analysis of random discrete structures, asymptotic analysis, exact and limiting distributions, and other fields of inquiry in computer science, probability theory, and enumerative combinatorics.