7 problems

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…

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

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

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…

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…