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
Presented under the auspices of the DIMACS Special Year on Massive Data Sets.
- Mordecai Golin, Hong Kong University of Science and Technology, Computer Science Department
- Julia Abrahams, Rutgers University, DIMACS firstname.lastname@example.org
Co-sponsored by DIMACS and the IEEE Information Theory Society.
We see considerable overlap in research interests between information
theory and algorithm design in the area of coding problems for data
compression, with particular focus on lossless tree structured codes such
as Huffmann codes and its variants. Unfortunately, there is not as much
overlap in our perspectives. Information theorists are more concerned with
entropy-based performance bounds and tradeoffs with respect to
additional criteria of interest in the context of data compression systems,
e.g. synchronization or buffer management. Computer scientists are more
with questions of efficiency and algorithm design. These very different
perspectives on similar problems has led to a lack of
communication, occasionally resulting in situations in which problems
considered difficult by one community are actually solvable
using tools well developed and understood by the other.
We thus think a small workshop on codes and trees discussing
both the algorthmic and information theoretic approaches would be
useful in promoting the exchange of ideas between the two communities. We
are planning a small 3 day workshop, October 5 - 7, 1998 at the DIMACS
Center, with support from DIMACS (including limited financial support for
participants). We plan to publish an edited version of the workshop proceedings in the DIMACS-AMS book series.
Possible topics covered at the workshop could include but are not limited
- tree structures compatible with code constraints
- minimum-cost search-trees and their variants
- infinite alphabet sources
- unequal costs coding
- codes with maximal length constraints
- coding for synchronization
- counting constrained trees
Next: Call for Participation
Contacting the Center
Document last modified on August 13, 1998.