73 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…

Core-structure conjecture. Under these hypotheses, every vertex incident with more than linearly many hyperedges shares a second common vertex with all those hyperedges.

Let $\pi$ be a distribution over $\Lambda_{k,r}$ and let $H_n(\pi,k,m)$ be the associated random uniquely extendable constraint system. Suppose that either $k\geq 4$ and…

Let $\pi$ be a distribution over $\Lambda_{k,r}$, and let $H_n(\pi,k,m)$ be the associated random uniquely extendable constraint system. Weakened-support conjecture. Theorem should…

Let $G$ be a finite group of order at least two, and let $H_n(\pi,k,m)$ be the random uniquely extendable constraint system arising from the group-equation model described in the s…

Let $k\geq 3$, and let $\mu$ be a distribution over the set $\Lambda_{k,r}$ of $k$-ary uniquely extendable constraint functions. Suppose that, if $k\geq 4$, every function in…

Let $k\frac{}{}$ and $r$ be fixed integers with $k\geq 3$ and $r\geq 2$. Let $d_k$ be the constant defined in the random $k$-XORSAT satisfiability-threshold theorem. Let $\Phi$ be…

Let $\mathfrak{B}$ be a first-order reduct of a finitely bounded homogeneous structure in a finite relational signature. The constraint satisfaction problem…

Tractability conjecture. If $\mathfrak{B}$ does not pp-construct $(\{0,1\};\operatorname{NAE})$, then

Finite Mal'tsev embedding conjecture. Any predicate over a finite domain with an infinite Mal'tsev embedding also has a finite Mal'tsev embedding. In particular, any predicate with…

Fix $d\geq 2$. A quantum assignment to a label-cover instance is $k$-compatible when the measurements associated with variables in every subinstance of Gaifman-graph diameter at mo…

Restricted CSP tractability conjecture. If the restricted $\operatorname{CSP}$-template does not rpp-construct $({\mathbb K}_3,{\mathbb L})$, then…

The tractability conjecture. If ${\mathbb A}$ does not pp-construct ${\mathbb K}_3$, then $\operatorname{CSP}({\mathbb A})$ is polynomial-time solvable.

Homomorphism-embedding CSP conjecture. There is a homogeneous Ramsey structure $\str H$ in a finite relational language, first-order bi-interpretable with $\str M$, such that the h…

Bodirsky–Pinsker conjecture. If $\str M$ is a first-order reduct of a finitely bounded homogeneous structure in a finite relational language, then either…

Bounded-width boundary conjecture. A homomorphism problem is $\mathbf{\Pi}^1_1$ iff it is not $\mathbf{\Sigma}^1_2$-complete iff it is bounded width.

Abelian embedding conjecture. For a distribution $\mu$ on $\Sigma^k$, Conclusion $$ holds if and only if $\mu$ admits no Abelian embedding.

A constraint satisfaction or optimization problem is a computational problem whose feasible assignments or candidate solutions can be evaluated by its constraints or objective func…

Let $k$ be a positive integer, and consider an instance of the two-variable linear system $2$-Lin-$k$ over $\mathbb{Z}_k$, with equations … An assignment is a map…

Pp-construction conjecture. If $\operatorname{PCSP}(G,H)$ is NP-hard, then $K_3$ has a pp-construction in $S$.

Let $H$ be a connected core on $k\geq 3$ vertices. Write $E_H$ for the edge relation of $H$, let $\langle E_H\rangle$ denote the relational clone generated by $E_H$, and let…

Let $A$ be a finite domain, let $\Gamma$ be a constraint language on $A$, and let $\QCSP(\Gamma)$ denote the quantified constraint satisfaction problem for $\Gamma$. A mighty tuple…

Completeness conjecture. In parts (a) and (b) of the cited dichotomy theorem, $\operatorname{SAT}_{matrix}(\mathcal{L})$ is $\mathrm{RE}$-complete, and…

Fractional-polymorphism classification conjecture. If $(\{0,1\};\operatorname{OIT})$ has no pp-construction in $\Gamma$, then $\operatorname{VCSP}(\Gamma)$ is in $\operatorname{P}$…