7 citations · 12 across the 4 of their papers we have counts for
4 papers · 1 filter
Finding a Winning Strategy for Wordle is NP-complete
Will Rosenbaum
In this paper, we give a formal definition of the popular word-guessing game Wordle. We show that, in general, determining if a given Wordle instance admits a winning strategy is N…
The Arboricity Captures the Complexity of Sampling Edges
Talya Eden, Dana Ron, Will Rosenbaum
In this paper, we revisit the problem of sampling edges in an unknown graph from a distribution that is (pointwise) almost uniform over . We consider the case where…
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…
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…