Announcements

CE Seminar by Funda Ergun

Author: COLLEGE OF ENGINEERING
Time: 11:00
Location: ENG 208

******************************

KOC UNIVERSITY

COLLEGE OF ENGINEERING

ENGINEERING SEMINAR SERIES

******************************

Speaker: Funda Ergun

Title: Finding Structure in Long Streams

Date: 24 May 2017Wednesday

Time: 11:00

Place: Eng 208

Host: Engin Erzin

 

Abstract

During the past two decades, the streaming model has emerged as a particularly apt way of viewing large data. This model assumes that data can only be accessed character by character in a sequential fashion, emulating data or read in real time as it is created. Streaming algorithms explore computation on such a stream with resources that are small compared to the data. The goal of such an algorithm typically is to perform its task using very small, usually polylogarithmic, memory (while, secondarily, working fast).

In this talk, we will focus on algorithms for discovering structure in long sequences. The algorithms we present  read the input left to right, as a stream, and output the structure that they detect as they go along. In particular, we will discuss detecting long increasing subsequences, inclusion of given patterns/words, periodicity, and existence of long palindromes. The algorithms we present require much smaller space than the input (polylogarithmic at worst), and their space use is optimal or near-optimal. We will also discuss some new results on discovering structure in the presence of a small number of errors in the input, making the algorithms more useful for real world problems, and the implications of imperfect input on the resource needs of an algorithm.

Bio

Funda Ergun is a professor in the Computer Science Department at Indiana University. She received her BS from Bilkent University and her PhD from Cornell University. Her research areas include randomized algorithms, big data algorithms, sublinear/streaming algorithms, and the algorithmic aspects of computer networks.