138 citations · 191 across the 22 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DS2019★ 1 cited
Smoothed complexity of local Max-Cut and binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +2
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most , where is the number of nodes in the graph and is a…
cs.CC2019
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein +1
The use of monotonicity and Tarski's theorem in existence proofs of equilibria is very widespread in economics, while Tarski's theorem is also often used for similar purposes in th…