This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

This edit request by an editor with a conflict of interest has now been answered.

• 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)[reply]

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)[reply]

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)[reply]