Title: On the power of Conditional Sampling

Description: Speaker: Dr. Sourav Chakraborty

Time: Monday, 15 January 2018, 10:30am
Venue: CC 109 Room, 01st Floor, New CSE Bldg.

Abstract:
In the modern world of big data and fast computing, it is essential to design super fast algorithms. Often reading the whole data is either too costly or time-consuming and sometimes not feasible. Property testing is a subject that deals with these challenges. It tries to design sub-linear algorithms for testing various properties of inputs. The key lies in the way the data is accessed by the algorithm.

One of the central problems in property testing and many other related subjects is testing if a distribution has certain a property - say whether a distribution on a finite set is uniform. The conventional way of accessing the distributions is by drawing random samples from the distributions. Unfortunately in this setting the number of samples that are necessary for testing properties of distribution is large enough and this makes the algorithms impractical is real life applications.

We define a new way of accessing the distribution using ``conditional-sampling oracle". This oracle can be used to design much faster algorithms for testing properties of distribution and thus makes the algorithm useful in practical scenarios. In a couple of recent ongoing projects, we show that the conditional oracle can be implemented in many real life problems and we have been able to show the usefulness of this model and our algorithms in practical purposes and others areas of research. This model also throws a number of interesting theoretical questions.


Speaker Profile:
Information about Dr. Sourav Chakraborty is available at: http://www.cmi.ac.in/~sourav/

Organization:
Chennai Mathematical Institute (CMI)



Host:
Prof. Nutan Limaye

Date: Monday, 15 January, 2018
Time: 10:30am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Saturday, 10 November, 2018 6:52am IST
Send Reminder: Yes  -  94 hours 1 minute before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
<seminar@iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)