982 citations · 2.8k across the 131 of their papers we have counts for
4 papers · 1 filter
Near Optimality in Covering and Packing Games by Exposing Global Information
Maria-Florina Balcan, Sara Krehbiel, Georgios Piliouras +1
Covering and packing problems can be modeled as games to encapsulate interesting social and engineering settings. These games have a high Price of Anarchy in their natural formulat…
The Complexity of Approximating a Bethe Equilibrium
Jinwoo Shin
This paper resolves a common complexity issue in the Bethe approximation of statistical physics and the Belief Propagation (BP) algorithm of artificial intelligence. The Bethe appr…
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
Ricardo Restrepo, Jinwoo Shin, Prasad Tetali +2
We study the hard-core model defined on independent sets, where each independent set I in a graph G is weighted proportionally to , for a positive real parameter . For…
Efficient Distributed Medium Access
Devavrat Shah, Jinwoo Shin, Prasad Tetali
Consider a wireless network of n nodes represented by a graph G=(V, E) where an edge (i,j) models the fact that transmissions of i and j interfere with each other, i.e. simultaneou…