Co-sponsored by DIMACS and the IEEE Information Theory Society.
8:00 - 8:45 Registration/Continental Breakfast 8:45 - 9:00 Welcome/Introductions 9:00 - 10:20 Julia Abrahams, Rutgers University Tutorial - Huffman Code Trees and Problem Variants: Some Open Questions 10:20 - 10:50 Break 10:50 - 11:20 Joy Thomas, IBM Huffman Algebras 11:20 - 11:50 Wojtek Szpankowski, Purdue Two Functional Equations Arising in Information Theory and the Analysis of Algorithms 11:50 - 12:20 Kingo Kobayashi, University of Electro Communications (with Mamoru Hoshi and Hiro Morita) Coding of Trees: From the Information-Theoretic Point of View 12:20 - 1:20 Lunch 1:20 - 2:40 Wolf Bein, University of Nevada - Las Vegas Tutorial-Monge Properties: Contemporary Tools for Efficient Algorithms 2:40 - 3:10 Lawrence L. Larmore, University of Nevada - Las Vegas Optimal Trees and the Monge Property 3:10 - 3:40 Break 3:40 - 4:10 Rudolf Fleischer, Max-Planck Institut Saarbrucken Self-Organizing Data Structures and Compression: A Survey 4:10 - 4:40 Mike Fredman, Rutgers University (with David M. Cohen, IDA) Weighted Binary Trees for Concurrent Searching 4:40 - 5:10 Mordecai Golin, Hong Kong University of Science and Technology (with Sze-Lok Chan) A Dynamic Programming Algorithm for Constructing Optimal "1"-Ended Binary Prefix-Free Codes 5:10 - 5:40 Bob Sedgewick, Princeton University (with J. Bentley) Is Quicksort Optimal? 5:40 Reception Dinner on own
Tuesday, October 6, 19988:15 - 9:00 Continental Breakfast 9:00 - 10:20 Veronique Bruyere, University of Mons-Hainaut Le Pentagone Tutorial- Codes: A Language Theoretic Approach 10:20 - 10:50 Dominique Perrin, Universite de Marne-la-Vallee Bifix Codes 10:50 - 11:20 Break 11:20 - 11:50 Ruy Luiz Milidiu, PUC-RJ (with Eduardo Sany Laber and Artur Alves Pessoa) New Results on Length Restricted Prefix Codes 11:50 - 12:20 Hiro Morita, University of Electro Communications (with Kingo Kobayashi and Mamoru Hoshi) Distribution Converter Using Prefix Trees 12:20 - 1:20 Lunch 1:20 - 1:50 Ian Munro, Waterloo (with Venatesh Raman) Succinct Tree Representations for Fast Navigation 1:50 - 2:20 David Benoit, Waterloo (with Ian Munro) Succinct Encoding of Ordinal Trees for Fast Traversal 2:20 - 2:50 Karthik Visweswariah, Princeton University (with Sanj Kulkarni and Sergio Verdu) Worst Case Bounds on Universal Variable-to-Fixed Length Source Codes 2:50 -3:20 Erik D. Demaine, Waterloo (with Ian Munro and Alex Lopez-Ortiz, University of New Brunswick) Adaptive Computation of the Intersection of a Collection of Sets 3:20 - 3:50 Break 3:50 - 4:20 Roberto De Prisco, MIT (with Alfredo De Santis) On the Redundancy and Data Expansion of Huffman Codes 4:20 - 4:50 Akiko Kato, UC San Diego and University of Tokyo Huffman-like Optimal Codes and Search Codes for Infinite Alphabets 4:50 - 5:20 Ion Mandoiu, Georgia Tech Optimum Extensions of Prefix Codes 5:20 - 5:50 Group Discussion-Problem Session 5:50 Group Dinner
Wednesday, October 7, 19988:15 - 9:00 Continental Breakfast 9:00 - 9:30 Stott Parker, UCLA The Construction of Huffman Codes is a Submodular ('Convex') Problem Over a Lattice of Binary Trees 9:30 - 10:00 Teresa M. Przytycka, Johns Hopkins University (with S. Rao Kosaraju and Ryan Borgstrom) On an Optimal Split Tree Problem 10:00 - 10:30 Eduardo Sany Laber, PUC-RJ (with Ruy Luiz Milidiu and Artur Alves Pessoa) Dynamic Huffman Coding 10:30 - 11:00 Break 11:00 - 11:30 Paul Tucker, UC San Diego (with T.C. Hu and M.T. Shing) Binary Search Trees and Binary Code Trees 11:30 - 12:00 Mihai Sipitca, Georgia Tech (with David Gillman) Lossless Encoding of DCT Coefficients for Video Compression 12:00 - 12:30 Sajal Das, U North Texas (with Amiya Bhattacharya) Predictive Location Management Using Lossless Compression 12:30 - 1:30 Lunch 1:30 - 2:00 Helmut Jurgensen, U Western Ontario and U Potsdam (with Stavros Konstantinidis, St. Mary's) Synchronization in the Presence of Noise 2:00 - 2:30 Yuriy Reznik, RealNetworks On Compact Level Partitioning of Digital Trees 2:30 - 3:00 Mamoru Hoshi, University of Electro Communications (with Te Sun Han) Homophonic Coding by the Interval Algorithm: Preliminary Considerations 3:00 - 3:30 Break 3:30 - 4:00 Gil I. Shamir, Notre Dame (with Neri Merhav, Technion) Low Complexity Sequential Lossless Coding for Piecewise Stationary Memoryless Sources 4:00 - 4:30 Artur Alves Pessoa, PUC-RJ (with Ruy Luiz Milidiu and Eduardo Sany Laber) Space-Economical Generation of Minimum Redundancy Codes 4:30 - 5:00 Andrej Brodnik, Lulea Technical University and IMFM, and Svante Carlsson, Lulea Technical University Sub-Linear Huffman Decoding: Some Theoretical and Practical Results 5:00 End Other participants: Pete Swaszek, U Rhode Island Mike Saks, Rutgers Janos Komlos, Rutgers Serap Savari, Bell Labs Fred Kochman, IDA Simon Litsyn, Tel-Aviv U Marty Cohn, Brandeis Xuerong Yong, HKUST and Rutgers Yuanping Zhang, HKUST and Rutgers Victor S. Miller, IDA