54 citations · 59 across the 6 of their papers we have counts for
4 papers · 1 filter
Randomly coloring graphs of bounded treewidth
Shai Vardi
We consider the problem of sampling a proper -coloring of a graph of maximal degree uniformly at random. We describe a new Markov chain for sampling colorings, and show that…
A note on the size of query trees
Shai Vardi
We consider query trees of graphs with degree bounded by a constant, . We give simple proofs that the size of a query tree is constant in expectation and w.h.p…
On the Probe Complexity of Local Computation Algorithms
Uriel Feige, Boaz Patt-Shamir, Shai Vardi
The Local Computation Algorithms (LCA) model is a computational model aimed at problem instances with huge inputs and output. For graph problems, the input graph is accessed using…
Fast Local Computation Algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi +1
For input , let denote the set of outputs that are the "legal" answers for a computational problem . Suppose and members of are so large that there is not t…