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