Tenth Seminar on Analysis of Algorithms

 

Berkeley, June 14 18, 2004

 

Technical Program

 

MONDAY, June 14

 

  8:45 - 9:00

WELCOME

  9:00 - 12:30

Chair: Wojtek Szpankowski

  9:00 - 10:00

Philippe Flajolet, "Singularity Analysis: A Perspective"

10:00 - 10:30

BREAK

10:30 - 11:00

Bruno Salvy, "On the Average-Case Complexity of Groebner Basis"

11:00 - 11:30

Alois Panholzer, "More Results on Priority Trees"

11:30 - 12:00

Daniele Gardy, "Tree Representations for Boolean Formulae with Commutativity and Associativity"

12:00 - 12:30

Bob Sedgewick, "Organizational Meeting "

12:30 - 2:00

LUNCH

  2:00 - 5:00

Chair: Svante Janson

  2:00 - 3:00

Brigitte Vallee, "Euclidean Dynamics"

  3:00 - 3:30

BREAK

  3:30 - 4:00

Guy Louchard, "The Moments Problem of Extreme-Value Related Distribution Functions"

  4:00 - 4:30

Pawel Hitczenko, "Computing the Walsh-Hadamard Transform"

  4:30 - 5:00

BREAK

5:00 - 5:30

Predrag Jelenkovic, Probabilistic Analysis of the Nearly Optimal Caching Algorithms in the WWW Environment

5:30 - 6:00

Bernard Gittenberger, Infinite-Dimensional Functional Equations and Gaussian Limiting Distributions

 

TUESDAY, June 15

 

9:00 - 12:30

Chair: Bob Sedgewick

9:00 - 10:00

Don Knuth, Notation

10:00 - 10:30

BREAK

10:30 - 11:00

Helmut Prodinger, "Redundant Number Systems and Applications in Cryptography"

11:00 - 11:30

Boris Pittel, "Limit Shapes for Random Square Young Tableaux and Plane Partitions"

11:30 - 12:00

Philippe Jacquet, "Analytic Information Theory: Hidden Markov Processes"

12:00 - 12:30

Alfredo Viola, "Exact Distribution of Displacements in Linear Probing Hashing with Buckets"

12:30 - 2:00

LUNCH

  2:00 - 5:00

Chair: Philippe Flajolet

  2:00 - 3:00

Svante Janson, "Limit Theorems for Urn Models"

  3:00 - 3:30

BREAK

  3:30 - 4:00

Conrado Martinez, "On Partial Sorting"

  4:00 - 4:30

Omer Egecioglu, "Combinatorics of a Polynomial Riemann Hypothesis"

  4:30 - 5:00

Marcos Kiwi, "Expected Length of the Longest Common Subsequence for Large Alphabet"

5:00 - 6:00

MSRI Reception

WEDNESDAY, June 16

  9:00 - 12:30

Chair: Helmut Prodinger

  9:00 - 10:00

Daniel Panario, "Polynomials Over Finite Fields: Random Properties and Algorithms"

10:00 - 10:30

Brigitte Chauvin, "Four Martingales in Binary Search Trees"

10:30 - 11:00

BREAK

11:00 - 11:30

H.-K. Hwang, "The Profile of Random Quadtrees"

11:30 - 12:30

Michael Drmota, "The Profile and Height of log n Trees"

12:30

FREE TIME

THURSDAY, June 17

  9:00 - 12:30

Chair: Jim Fill

  9:00 - 10:00

Persi Diaconis, "Conditioned Limit Theorems"

10:00 - 10:30

BREAK

10:30 - 11:00

Wojtek Szpankowski, "From Pattern Matching to Suffix Trees"

11:00 - 11:30

Mark Ward, "Analysis of Error-Resilient LZ'77"

11:30 - 12:00

Julien Fayolle, "Suffix Trees and Simple Sources"

12:00 - 12:30

Chuck Knessl, "Applications of Applied Mathematics Methods to the Analysis of Algorithms and Tree Properties"

12:30 - 2:00

LUNCH

  2:00 - 5:00

Chair: Brigitte Vallee

  2:00 - 3:00

Jim Fill, "Gaussian Random Fields, Small Deviations, Random Sums, Mellin Transforms, and Reversion"

  3:00 - 3:30

BREAK

  3:30 - 4:00

Hosam Mahmoud, " Diagonal Polya Processes"

  4:00 - 4:30

Vincent Puyhaubert, Analytic Urns of Triangular Form

4:30 - 5:00

BREAK

5:00 - 5:30

Moritz Maass, Approximate Indexing with Tries

5:30 - 6:00

Alberto Apostolico, "Issues in the Discovery and use of Motif Patterns"

FRIDAY, June 18

  9:00 - 12:30

Chair: Gadiel Seroussi

  9:00 - 10:00

Richard Karp, "Optimal Adaptive Flow Distribution"

10:00 - 10:30

BREAK

10:30 - 11:00

Venkat Anantharam, A Measure-Theoretic Look at the Generalized Distributive Law

11:00 - 11:30

Markus Nebel, "On a Modified Boyer-Moore-Horspool Algorithm"

11:30 - 12:00

Richard Ladner, "The Analysis of Optimal Stream Merging Solutions for Media-on-Demand"

12:00 - 12:30

Greg Sorkin, "A Linear-Expected-Time Algorithm for Sparse Random Instances of Max Cut and Other Max 2-CSP"

12:30 - 2:00

LUNCH

  2:00 - 5:00

Chair: Philippe Jacquet

  2:00 - 3:00

David Aldous, "Maximum Flow Through a Random Network: An Illustration of the Cavity Method"

  3:00 - 3:30

BREAK

  3:30 - 4:00

Mordecai Golin, "Generalizing the Kraft-McMillan Inequality to Restricted Languages"

  4:00 - 4:30

Serap Savari, "Compression of Words Over a Partially Commutative Alphabet"

4:30 - 5:00

BREAK

  5:00 - 5:30

Gadiel Seroussi, "Universal Types, Binary Trees, and Simulation of Individual Sequences"

5:30 - 6:00

Mike Luby, "Fountain Codes Information Theoretic Optimal Codes for Data Transport Applications"