13 problems

A label-cover instance consists of variables, an alphabet, and constraints between variable pairs; a constraint is bijective when each label on either variable determines exactly o…

Let an instance of the Unique Games Problem consist of a graph, a set of colors, and a matching of the colors for each edge. The value of an instance is the largest fraction of edg…

Plurality is Stablest conjecture. If $\rho\geq0$ and $\mathbb{E}f=\frac1k\sum_{j=1}^{k}e_j$, then

Fix an integer $d>1$. Let $\Phi=(X,Y,\Psi,W)$ be a weighted bipartite $d$-to-$1$ label-cover instance with label sets $\{1,\ldots,R\}$ and $\{1,\ldots,R/d\}$ and total edge weight…

Let $G={\rangle (V,E),2R,\Psi\langle}$ be a label-cover instance whose constraints are alpha-constraints, where an alpha-constraint is defined by permutations…

Let $\Phi$ be a $d$-to-$1$ label-cover instance: its constraints are binary, form a bipartite graph, and for each constraint every label on one variable admits one label on the oth…

Sharp hardness consequence. For every $\varepsilon>0$, it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $\alpha_{3}+\varepsilon$.

MAX-$k$-CUT analogue. An analogue of the relevant MAX-CUT theorem should hold for MAX-$k$-CUT.

Let $\Psi=(L\cup R,E,\Sigma_L,\Sigma_R,\Phi)$ be a Rich $2$-to-$1$ Games instance with $|\Sigma_L|=n$ and $|\Sigma_R|=n/2$. For each $u\in L$, the distribution of partitions of…

A Unique-Games instance is a 1-to-1 Games instance: a 2-Prover-1-Round Games instance in which the two alphabets have equal size and every constraint is a bijection between them. F…

Weaker forms of the Max-Cut Conjecture. The problem

Gap-ETH. There exist constants $\epsilon,c>0$ such that no algorithm running in time $O(2^{cn})$ can distinguish between a satisfiable $3$-SAT formula and a $3$-SAT formula with at…

Consider a graph whose edges carry permutation constraints on a set of $n$ colors. Given $\epsilon,\delta>0$, distinguish between the promise that no coloring satisfies more than a…