19 citations · 39 across the 4 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012
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…
cs.CC2012★ 19 cited
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…