19 citations · 39 across the 4 of their papers we have counts for
5 papers
On the Power of Conditional Samples in Distribution Testing
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh +1
In this paper we define and examine the power of the {\em conditional-sampling} oracle in the context of distribution-property testing. The conditional-sampling oracle for a discre…
The non-adaptive query complexity of testing k-parities
Harry Buhrman, David Garcia-Soriano, Arie Matsliah +1
We prove tight bounds of Theta(k log k) queries for non-adaptively testing whether a function f:{0,1}^n -> {0,1} is a k-parity or far from any k-parity. The lower bound combines a…
New Results on Quantum Property Testing
Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability d…
Hardness and Algorithms for Rainbow Connectivity
Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted…
Hardness and Algorithms for Rainbow Connection
Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1
An edge-colored graph is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connection} of a connected graph…