Talk:Unique games conjecture

Failed to Parse

When I load this page, there's a big red "Failed to Parse" on it at the bottom of the "Unique Label Cover" section. Can someone (who knows more about the UGC) take a look at that? — Preceding unsigned comment added by 142.244.222.54 (talk) 18:40, 9 February 2014 (UTC)

Missing

This page is missing any substantial discussion of why the UGC is important. Also missing are equivalent forms of the conjecture, e.g., 2LIN(q). 131.215.48.236 (talk) 22:29, 29 May 2008 (UTC)

Clarify for non-experts

I've added another reference that is good for non-experts, and made another one more prominent. We should mine them for insights to improve this important article, helping make it more accessible.★NealMcB★ (talk) 01:08, 30 October 2012 (UTC)

The UGC bound for Max-2-SAT

In this reference, the bound β achieved on Max-2-SAT in Theorem 3 is .943943... which is larger than .940... Is this an error, or does another paper prove the tight bound? --125.34.6.194 (talk) 02:38, 27 October 2013 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Unique games conjecture. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://web.archive.org/web/20120610155513/http://www.cs.princeton.edu:80/~dsteurer/subexpug.pdf to http://www.cs.princeton.edu/~dsteurer/subexpug.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:04, 20 July 2016 (UTC)

Unique label cover

For each edge, the colors on the two vertices are restricted to some particular ordered pairs Do you mean to say that there are k ordered pairs and each color appears at each vertex exactly once? (otherwise I don't see how you would get uniqueness) This means that an instance of label cover with unique constraints over an alphabet of size k can be represented as a directed graph together with a collection of permutations πe: [k] → [k], one for each edge e of the graph Such instances are strongly constrained in the sense that the colour of a vertex uniquely defines the colours of its neighbours

That is what it usually means, yes. It isn't a very interesting problem if you're asking for all the constraints to be satisfied (just pick a color for one vertex and propagate) but the problem is, for cases that can't all be satisfied, to satisfy approximately as many constraints as possible. —David Eppstein (talk) 20:52, 26 October 2018 (UTC)

which English to use

because there are uses of the different colour/color Awesomecat713 (talk) 16:28, 25 June 2021 (UTC)

Khot 2002 uses "color" so I think as the foundational document for this topic that is what we should follow. Our article was created in 2005 but the "colour" spelling appears to have been added in 2010, much later. —David Eppstein (talk) 16:50, 25 June 2021 (UTC)

Proposed edit

• Specific text to be added or removed: I actually already made the edit but then was informed that it might violate the COI policy because it involves a citation to a paper of mine, so I'm flagging this for review as suggested by Jay8g on my talk page. The relevant edits are [09:26, 15 January 2025] and the associated edit to the references is [09:13, 15 January 2025]
• Reason for the change: I wanted to add the connection to computational topology. 1-cohomology localization is only one of three problems I am aware of that are "UGC-complete" in the sense that their inapproximability is *equivalent* to the UGC (the other two be unique label cover and Max2Lin).
• References supporting change: The potential COI is that the connection to cohomology localization was made in a paper of mine & Tucker-Foltz, so I added a reference to that. The paper is relatively recent so I don't think it has appeared in secondary sources, surveys, etc. yet, and I do not know of other sources that have made this connection. (I'm really not trying to citation spam - I am trying to make a good faith reference to something I think is a valuable addition to this page.) However, our paper was published in a standard, well-regarded venue (Symp. Comp. Geom., "SoCG"), and is cited in the introduction on p.2 of https://doi.org/10.4230/LIPIcs.SoCG.2020.21, where they write "For an overview of the unique games conjecture and its impact on computational topology we refer the reader to the work of Growchow [sic] and Tucker-Foltz [19].", where [19] in that paper is the same reference I added to this page.

Joshuagmath (talk) 20:42, 16 January 2025 (UTC)

Already done and seems fine to me. Thank you for going through the COI edit request process; in the future you should continue to do this when adding citations to your own papers. Rusalkii (talk) 06:52, 17 January 2025 (UTC)

thank you for reviewing! Yes, now that I know about the process I will do it in the future before edits with my own citations rather than after. Joshuagmath (talk) 18:23, 17 January 2025 (UTC)