Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On the power of Conditional Sampling
Speaker:Sourav Chakraborty
coming from:Indian Statistical Institute, Kolkata, India
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 28 September 2018
Duration:45 Minutes
Building:E1 4
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 a certain property - say whether a distribution on a finite set is uniform. The conventional way of accessing the distributions is by drawing samples according to the distributions. Unfortunately, in this setting the number of samples that are necessary for testing properties of distribution (for most natural properties) is polynomial in the size of support of the distribution. Thus when the support is relatively big the algorithms become impractical in 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 fact, we can show that any label-invariant property of distribution can be tested using a constant number of conditional samples.

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.

Name(s):Nitin Saurabh
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Nitin Saurabh, 09/25/2018 04:34 PM
Last modified:
halma/MPII/DE, 04/18/2019 12:01 AM
  • Nitin Saurabh, 09/25/2018 04:34 PM -- Created document.