Unique Games Conjecture - Discussion and Alternatives

Discussion and Alternatives

Currently there is no consensus regarding the truth of the unique games conjecture. Certain stronger forms of the conjecture have been disproved.

A different form of the conjecture postulates that distinguishing the case when the value of a unique game is at least 1 − δ from the case when the value is at most ε is impossible for polynomial-time algorithms (but perhaps not NP-hard). This form of the conjecture would still be useful for applications in hardness of approximation.

The constant δ > 0 in the above formulations of the conjecture is necessary unless P = NP. If the uniqueness requirement is removed the corresponding statement is known to be true by the parallel repetition theorem, even when δ = 0.

In 2010, Arora, Barak and Steurer found a subexponential time approximation algorithm for unique games problem.

Read more about this topic:  Unique Games Conjecture

Famous quotes containing the words discussion and, discussion and/or alternatives:

    Opinions are formed in a process of open discussion and public debate, and where no opportunity for the forming of opinions exists, there may be moods—moods of the masses and moods of individuals, the latter no less fickle and unreliable than the former—but no opinion.
    Hannah Arendt (1906–1975)

    It was heady stuff, recognizing ourselves as an oppressed class, but the level of discussion was poor. We explained systemic discrimination, and men looked prettily confused and said: “But, I like women.”
    Jane O’Reilly, U.S. feminist and humorist. The Girl I Left Behind, ch. 2 (1980)

    The last alternatives they face
    Of face, without the life to save,
    Being from all salvation weaned
    A stag charged both at heel and head:
    Who would come back is turned a fiend
    Instructed by the fiery dead.
    Allen Tate (1899–1979)