BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/463
DTSTAMP:20230914T125925Z
SUMMARY:Understanding Global Properties of Data Sets from Local Observation
s
DESCRIPTION:Speaker: Sofya Raskhodnikova (The Pennsylvania State University
& Boston University)\n\nAbstract: \nSuppose we are given a list of number
s and we wish to determine whether it is sorted in increasing order. That
problem obviously requires reading the entire list. However\, it turns out
that if we know in advance that our list is either sorted or far from sor
ted\, we can perform the test by examining only a small portion of the lis
t. This is an example of a global property of a data set that we can under
stand by making a few local observations. As data of all types gets easier
to obtain and cheaper to store\, data sets are becoming increasingly larg
e. Consequently\, there is a need to perform computational tasks on massiv
e data sets. What useful computations can be performed on a data set when
reading all of it is prohibitively expensive? This question\, fundamental
to several fields\, is at the heart of a research area\, called Sublinear
Algorithms\, that has provided important insights into fast approximate co
mputation. In this talk\, we will give a few examples of specific problems
that can be solved while making only local observations\, starting with t
he sorting example and moving on to simple analysis of images\, comparing
and compressing documents\, and understanding properties of functions. We
will also present an application of these ideas to an area (namely\, data
privacy)\, where extreme efficiency is not a requirement per se\, but help
s to guarantee other properties. Speaker Bio: Sofya Raskhodnikova is an as
sociate professor of Computer Science and Engineering at Penn State. She r
eceived her Ph.D. from MIT. Prior to joining Penn State in 2007\, she was
a postdoctoral fellow at the Hebrew University of Jerusalem and the Weizma
nn Institute of Science\, and a visiting scholar at the Institute for Pure
and Applied Mathematics at UCLA. Currently\, she is on sabbatical at Bost
on University. Dr. Raskhodnikova works in the areas of randomized and appr
oximation algorithms. Her main interest is the design and analysis of subl
inear-time algorithms for combinatorial problems. Sublinear algorithms pro
duce approximate answers after examining only a tiny portion of the data.
Such algorithms are important for dealing with massive data sets.\n
URL:https://www.tcs.tifr.res.in/web/events/463
DTSTART;TZID=Asia/Kolkata:20140225T100000
DTEND;TZID=Asia/Kolkata:20140225T110000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR