MAXCUT Is UGC-hard to Approximate [KKMO07]
Date
Jan 3, 2018 10:15 AM
Event
Student-led Computational Complexity seminar, Weizmann Institute of Science
Location
Goldsmith 108, Weizmann Institute of Science
[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. 2007. Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? SIAM Journal on Computing 37, 1 (January 2007), 319–357. DOI:https://doi.org/10.1137/S0097539705447372
