Your submission is now in Draft mode.

Once it's ready, please submit your draft for review by our team of Community Moderators. Thank you!

Submit Essay

Once you submit your essay, you can no longer edit it.

Pending

This content now needs to be approved by community moderators.

Submitted

This essay was submitted and is waiting for review.

Unique Games Conjecture by 2030

Question

The Unique Games Conjecture (UGC) is a conjecture made by Nevanlinna Prize winner Subhash Khot of NYU in 2002. It states that the Unique Games problem is NP-hard, and is one of the famous open problems in computational complexity theory. It especially has implications in hardness of approximation; for instance, it implies that the problem of approximating maximum cut for graphs by a better constant than given by the Goemans-Williamson algorithm is NP-hard.

At the 2019-2020 Tel Aviv Theory Fest, MIT professor Elchanan Mossel and NYU professor and Khot made a bet that a correct proof of UGC will be uploaded to arXiv by 2030. In early 2018, Khot, along with Dor Minzer and Muli Safra, made a significant advance toward proving UGC in a paper. Harvard professor Boaz Barak agreed to referee the bet.

Will the Unique Games Conjecture be proved by 2030?

This question resolves positively if Boaz Barak writes publicly (on Twitter, a blog, or elsewhere) that Elchanan Mossel has won the bet. It resolves negatively if he announces Subhash Khot has won. If there is no announcement by the resolve date, then it resolves positively if there is a peer reviewed paper that was originally uploaded to the ArXiv in 2030 which is accepted in a major mathematics journal or computer science conference by the resolve date. Else, it resolves negatively.

Make a Prediction

Prediction

Note: this question resolved before its original close time. All of your predictions came after the resolution, so you did not gain (or lose) any points for it.

Note: this question resolved before its original close time. You earned points up until the question resolution, but not afterwards.

Current points depend on your prediction, the community's prediction, and the result. Your total earned points are averaged over the lifetime of the question, so predict early to get as many points as possible! See the FAQ.