# Questions tagged [unique-games-conjecture]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
48 views

### Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$

$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be ...
217 views

### Why does Dinur's proof of the PCP theorem fail to work for unique games?

What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
57 views

### Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading:  Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 of [...
113 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 ...
178 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 ...
71 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, ...
92 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 ...
420 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 ...
583 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$, ...
467 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 ...
1k views

358 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 ...
810 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 ...
393 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 ...
268 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 ?
822 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"?
560 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 ...
451 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 ...