40 citations · 242 across the 33 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
math.CO2016
Sperner's colorings and optimal partitioning of the simplex
Maryam Mirzakhani, Jan Vondrak
We discuss coloring and partitioning questions related to Sperner's Lemma, originally motivated by an application in hardness of approximation. Informally, we call a partitioning o…
cs.GT2016
When Are Welfare Guarantees Robust?
Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák
Computational and economic results suggest that social welfare maximization and combinatorial auction design are much easier when bidders' valuations satisfy the "gross substitutes…
cs.DS2016★ 4 cited
Computing the Independence Polynomial: from the Tree Threshold down to the Roots
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
We study an algorithm for approximating the multivariate independence polynomial , with negative and complex arguments, an object that has strong connections to comb…