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