[Colloquium] TTIC Colloquium (Please note special date): Prof. Funda Ergun, Indiana Univ & Simon Fraser Univ

[Dawn Ellis]

When:     *Thursday, July 31st at 11am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Speaker:  Prof. Funda Ergun, Indiana Univ Bloomington and Simon Fraser
University

Title: Palindrome Recognition In The Streaming Model

Abstract:

In this talk we are interested in finding palindromes in a given string
within
the streaming context.

A palindrome is a string which reads forwards the same as backwards,
e.g., “racecar”.

A streaming algorithm is one where the input is read in a sequential manner
from
left to right in one or more passes.  This model is especially relevant
when the
input is too large to fit in main memory; thus it is required that a
streaming
algorithm use space sublinear in input size.

We would like to find all (long/longest) palindromes in a string while
staying within the limits
of the streaming model. In this talk we present three algorithms for
finding the longest
palindrome/all long palindromes in a given stream of length n.  One is an
exact
algorithm that makes two passes over the input and uses O(sqrt(n))
space to find the longest
palindrome in a given stream.
The other two are approximations (in terms of the lengths of the
palindromes that they return);
one is a one-pass O(sqrt(n)) space algorithm with additive error,
which returns the
lengths and locations of all palindromes in the input. The other is a one
pass
O(log(n)) space algorithm for finding the longest palindrome, which
instead returns one with
length at most a small multiplicative factor away from that of the
longest palindrome.
All algorithms are randomized, and run in linear time.

While logarithmic space is desirable, we show that there is a sqrt(n)
space bound for
a one randomized pass algorithm with a sqrt(n) additive approximation
factor.

Joint work with Petra Berenbrink, Frederik Mallmann-Trenn, and Erfan Sadeqi
Azer
of Simon Fraser University.

Host:  Jinbo Xu, j3xu at ttic.edu


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140723/38ce10cd/attachment.htm