ColloquiaAmihood Amir's talk - Wednesday, June 5

[Margery Ishmael]

Wednesday, June 5, 2002
2:30 pm
Ryerson 251

AMIHOOD AMIR, Bar-Ilan University, Israel (on leave at AT&T Labs - Research)

Title: "Approximate Pattern Matching - the Hamming Distance Case."

Abstract: Many different meanings can be assigned to the words 
"approximation" of pattern matching. One possibility is that of allowing 
"local" errors.

Intuitively, we group under the label "local" errors that take place in a 
bounded location, as opposed to changes that permeate the entire data (e.g. 
scaling, rotation).

Specifically, consider the most limited local error -- the mismatch. This 
error occurs in a single symbol and effects only its location. In contrast, 
insertions and deletions have a global effect, although the error itself is 
confined to a single location.

We discuss known techniques and upper bounds for matching with the mismatch 
local error. We also present a new algorithm that finds in a length-n text 
all locations where a length-m pattern matches with
at most k mismatches, in time O(n sqrt(k log k).

The talk uses the approximate Hamming distance problem only as an
excuse for a quick review of some main techniques in the field. Some
of these may come in handy even if the listener is not (heaven forbid)
a researcher in pattern matching. http://www.cs.biu.ac.il/~amir/

(The new result is joint with Moshe Lewenstein and Ely Porat.)

Host: Professor Janos Simon

*Refreshments will be served after the talk in Ryerson 255*
Persons with a disability who may need assistance should call 834-8977 in 
advance.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977  fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=