← All problems

Unique Games Conjecture

For every ε,δ>0\varepsilon,\delta>0, does there exist an alphabet size qq such that it is NP-hard to distinguish Unique Games instances with optimum at least 1ε1-\varepsilon from those with optimum at most δ\delta?

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li