hp home products & services support solutions how to buy
spacer
hp logo - invent
corner hp labs corner
search search
contact hp contact hp
hp labs home hp labs home
hpl advanced studies hpl advanced studies
information theory research information theory research
corner corner
spacer

hp labs
information theory seminar

Thursday, January 3, 2002, 2:00-4:00PM

Half Dome Conference Room, 3L
HP Labs Palo Alto

Two lectures on applications of analytic techniques to 
information theory and finite field algorithms
TALK 1 (2:00-3:00)

THE PRECISE REDUNDANCY RATE PROBLEM

Prof. Wojciech Szpankowski
Department of Computer Science
Purdue University
W. Lafayette, IN 47907
U.S.A.

Recent years have seen a resurgence of interest in redundancy rates of lossless coding. The redundancy rate problem for a class of sources consists in determining by how much the actual code length exceeds the optimal code length. In a minimax scenario one finds the maximal redundancy over all sources within a certain class while in the average scenario one computes the average redundancy over all possible source sequences. The redundancy rate problem is typical of a situation where second-order asymptotics play a crucial role (since the leading term of the optimal code length is known to be the entropy of the source). This problem is an ideal candidate for ``analytic information theory'',  that applies analytic tools (i.e., complex analysis) to information theory. Here we focus on the precise maximal minimax redundancy: We shall show how to replace the 1987 Shtarkov inequality for the minimax  redundancy by a precise equality. Then we survey our recent results on the redundancy rate problem obtained by analytic methods. In particular, we present precise results for the redundancy of Shannon codes, Huffman codes, minimax redundancy for memoryless sources Markov sources, and renewal processes. We shall also briefly discuss some analytic tools used to establish these results, such as Fourier analysis, Gleichverteilung (i.e., sequence distributed) mod 1, generating functions, singularity analysis, Mellin transform, the saddle point method, and analytic depoissoinization.

Host: Marcelo Weinberger


TALK 2 (3:00-4:00)

ANALYSIS OF RABIN'S IRREDUCIBILITY TEST FOR POLYNOMIALS OVER FINITE FIELDS

Prof. Alfredo Viola
Computer Science Institute
University of Uruguay
 

We give a precise average-case analysis of Rabin's algorithm for testing the irreducibility of polynomials over finite fields. The main technical contribution of the paper is the study of the probability that a random polynomial of degree n contains an irreducible factor of degree dividing several maximal divisors of the degree n. We then study the expected value and the variance of the number of operations performed by the algorithm. We present an exact analysis when n=p1 and n=p1p2 for p1, p2 prime numbers, and an asymptotic analysis for the general case. Our method generalizes to other algorithms that deal with similar divisor conditions. In particular, we analyze the average-case number of operations for two variants of Rabin's algorithm, and determine the ordering of prime divisors of n that minimizes the leading factor.

This is a joint work with Daniel Panario, Boris Pittel and Bruce Richmond

Host: Gadiel Serouss

 

printing icon
printing instructions printing instructions
Privacy Statement Legal Notices © 1994-2000 Hewlett-Packard Company