max planck institut
informatik

# 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)
Title: On the power of Conditional Sampling Sourav Chakraborty Indian Statistical Institute, Kolkata, India AG1 Mittagsseminar (own work) D1, MMCIWe use this to send out email in the morning. AG Audience English
Date: Friday, 28 September 2018 13:00 45 Minutes Saarbrücken E1 4 023
 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