Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [unique-games-conjecture]

The tag has no usage guidance.

2
votes
1answer
99 views

Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $A$ by $$ f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}. $$ Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
1answer
147 views

Proof of Majority is stablest in “reverse” in the MAXCUT hardness paper by Khot et al

This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say ...
1
vote
0answers
56 views

Sparse-cut approximation for well connected graphs

Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$. If I understand UGC correctly, ...
3
votes
0answers
86 views

Some questions about the Ryan O'Donnel and Yuan Zhou's paper “Approximability and proof complexity”

My question is particularly about the set-up in section $8$ (``Analysis of the KV Max-Cut instances") of the paper, https://arxiv.org/pdf/1211.1958.pdf. What they call the Khot-Vishnoi UG instance ...
1
vote
1answer
393 views

What are multiple rounds of SOS/Lasserre hierarchy?

Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things? Or to take a ...
1
vote
1answer
422 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
3
votes
1answer
378 views

What is a “level-r pseudo expectation functional”?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
8
votes
1answer
690 views

About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \...
5
votes
1answer
445 views

Unique Games versus SDP procedures

Unique Games results provide very interesting barriers to results through semidefinite programming. Lovasz theta ($\vartheta(G)$) function is an incarnation of SDP. Is UG conjecture true $\iff \...
9
votes
1answer
290 views

A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
21
votes
1answer
677 views

What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

There are many inapproximability results which rely on the unique games conjecture. For example, Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a ...
3
votes
1answer
383 views

Consequences of Unique Games being a NPI problem

Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation ...
7
votes
1answer
251 views

Problems that are hard w.r.t UGC-hardness of VERTEX COVER

Are there any problems $P$ such that an $\alpha$-approximation for $P$ (for soem choice of $\alpha$) would imply a better than 2-approximation for VERTEX COVER, which would be hard via the UGC ?
16
votes
2answers
740 views

Is there a simple argument that shows that the unique games conjecture implies the PCP theorem

how can one show that what is relation between "Unique games conjecture" and "PCP theorem"? how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?
16
votes
3answers
531 views

UGC hardness of the predicate $NAE(x_1, …, x_\ell)$ for $x_i \in GF(k)$?

Background: In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary ...
19
votes
1answer
407 views

Visualizing Unique Games

How would you design a picture to illustrate the unique games conjecture? This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be ...
4
votes
1answer
215 views

Unique games conjecture - edge permutations

What do the edge permuations in the unique games conjecture represent?
22
votes
2answers
554 views

What evidence do we have for (and against) Unique Games Conjecture?

Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory. What evidence do we have for it? What evidence do we have against it?