All reports by Author Sourav Chakraborty:

__
TR13-142
| 11th October 2013
__

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni#### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

Revisions: 2

__
TR12-154
| 31st October 2012
__

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah#### On the Power of Conditional Samples in Distribution Testing

Revisions: 1

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>>

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>