44 citations · 165 across the 21 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2020★ 13 cited
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky +2
We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-cas…
cs.CC2019★ 1 cited
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
Jess Banks, Luca Trevisan
We prove that in sparse Erdős-Rényi graphs of average degree , the vector chromatic number (the relaxation of chromatic number coming from the Lovàsz theta function) is typicall…
cs.CC2017
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
Jess Banks, Robert Kleinberg, Cristopher Moore
We derive upper and lower bounds on the degree for which the Lovász function, or equivalently sum-of-squares proofs with degree two, can refute the existence of a $…