Ubiquitous Pattern Matching and Its Applications (Biology, Security, Multimedia)

------------------------------------------------------------------
                        Joint Seminar
Department of Computer Science and IEEE Information Theory Society
-------------------------------------------------------------------

Speaker:	Professor Wojciech Szpankowski
		Purdue University

Title:		"Ubiquitous Pattern Matching and Its Applications
		 (Biology, Security, Multimedia)"

Date:		Friday, 19 May 2006

Time:		11:00 am - 12 noon

Venue:		Room 1504 (near lift nos. 25/26)
		HKUST

Abstarct:

Pattern matching comes in many flavors: In the string matching problem,
for a given string one counts the number of its occurrences in a text. In
the subsequence pattern matching, also known as the hidden word problem,
we search for a given subsequence rather than a string. Finally, in the
repetitive pattern matching we aim at determining how long it takes for a
prefix of a text to reappear somewhere in the text. We apply probabilistic
and analytic tools of combinatorics and analysis of algorithms to discover
general laws of pattern occurrences. An immediate consequence of our
results is the possibility to set thresholds at which the appearance of a
pattern in given text starts being `meaningful'.

In this talk, we first discuss some applications of string matching
methodology to biological sequence analysis; in particular, to the problem
of finding weak signals and avoiding artifacts. We then use the approach
of hidden words to construct a reliable threshold for the intrusion
detection in detecting anomalies. Then, we present a video compression
scheme based on a two-dimensional self-repetitive pattern matching (i.e.,
a lossy extension of the Lempel-Ziv scheme). We conclude this talk with a
novel application of the repetitive pattern matching to an error-resilient
Lempel-Ziv77 scheme.


The talk slides are available at
http://www.cs.purdue.edu/homes/spa/talks/pm-h2.pdf


*****************
Biography:

Wojciech Szpankowski received his M.S. and Ph.D. degrees in Electrical and
Computer Engineering from the Technical University of Gdansk in 1976 and
1980, respectively.  Currently, he is Professor of Computer Science (and
by courtesy of Electrical & Computing Engineering) at Purdue University.
In 1992 he was Professeur Invite at INRIA-Rocquencourt, France, and in
1999 he was Visiting Professor at Stanford University.Dr. Szpankowski's
research interests cover analysis of algorithms, information theory,
bioinformatics, analytic combinatorics, stability problems, and applied
probability.  He has published over 150 papers on these topics.  His
recent work is mostly devoted to probabilistic analysis and design of
algorithms on sequences and applications of analytic tools to problems of
information theory and biology.  His book "Average Case Analysis of
Algorithms on Sequences" was published by John Wiley & Sons in 2001.

Dr. Szpankowski has been a guest editor for several journals including the
IEEE Transactions on Information Theory.  He is on the editorial boards of
Theoretical Computer Science, IEEE Trans. Information Theory, ACM Trans.
Algorithms, Combinatorics, Probability, and Computing, and Foundation and
Trends in Communications and Information Theory. He is a Fellow of the
IEEE.