54 citations · 93 across the 13 of their papers we have counts for
4 papers · 1 filter
A Parallelizable Acceleration Framework for Packing Linear Programs
Palma London, Shai Vardi, Adam Wierman +1
This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is smal…
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…