5 citations · 6 across the 8 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.CC2021
Sum-of-Squares Lower Bounds for Sparse Independent Set
Chris Jones, Aaron Potechin, Goutham Rajendran +2
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems.…
cs.DS2021
Certifying solution geometry in random CSPs: counts, clusters and balance
Jun-Ting Hsieh, Sidhanth Mohanty, Jeff Xu
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the de…