7 citations · 18 across the 15 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017★ 2 cited
Lower Bounds for Approximating Graph Parameters via Communication Complexity
Talya Eden, Will Rosenbaum
In a celebrated work, Blais, Brody, and Matulef developed a technique for proving property testing lower bounds via reductions from communication complexity. Their work focused on…
cs.CC2017
On Sampling Edges Almost Uniformly
Talya Eden, Will Rosenbaum
We consider the problem of sampling an edge almost uniformly from an unknown graph, . Access to the graph is provided via queries of the following types: (1) uniform ve…