DIMACS Workshop on Codes and Trees: Algorithmic and Information Theoretic Approaches

October 5 - 7, 1998
DIMACS Center, CoRE Building (Room 431), Rutgers University, Piscataway, NJ

Mordecai Golin, Hong Kong University of Science and Technology, Computer Science Department golin@cs.ust.hk
Julia Abrahams, Rutgers University, DIMACS abrahams@dimacs.rutgers.edu
Presented under the auspices of the DIMACS Special Year on Massive Data Sets.

Co-sponsored by DIMACS and the IEEE Information Theory Society.

Workshop Program:

Monday, October 5, 1998

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, 1998

8: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, 1998

8: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

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on October 2, 1998.