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