Robust Factorizations and Colorings of Tensor Graphs

Joshua Brakensiek, Sami Davies

Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around SDP-based rounding. However, it is likely that importan…