|Date: Friday, January 26, 2018
Location: 1084 East Hall (4:10 PM to 5:00 PM)
Title: Property testing and its variants: Formal models for big data algorithms
Abstract: Big data is the buzzword used to indicate the massive amounts of information that gets generated on the internet on a daily basis. Classical algorithms, whose running times are proportional to the lengths of their inputs, are not suitable to analyze big data because of the prohibitive amounts of time that they would take to run. It is in this context that the study of sublinear-time algorithms, which are algorithms running in time sublinear in the length of their inputs, become important. Property testing [Rubinfeld & Sudan '96, Goldreich, Goldwasser & Ron '98] is one of the most well-studied formal frameworks of sublinear-time algorithms.
The traditional definition of property testing abstracts datasets as functions and assumes that an algorithm (also called tester) can query points in the domain of a function to obtain the corresponding values. The task of the tester is to distinguish, with probability 2/3, between the case that the function f being queried belongs to a set (property) P and the case that f is `far' from every function in P, for an appropriate distance notion. In this talk, we will define property testing, see some main results in the area and finally, go on to present some generalizations of the traditional property testing model that accounts for the possibility of errors in datasets.
Speaker: Nithin Varma
Institution: Boston University
Event Organizer: Audra McMillan email@example.com