Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let A be a finite relational structure, and let A be its polymorphism clone. Let 1 be the clone of projections on a two-element set, and let an h1 clone homomorphism mean a homomorphism preserving identities of height 1. Core-free finite…
Let ω denote the exponent of matrix multiplication, equivalently the asymptotic exponent governing the border rank of the matrix multiplication tensors. Exponent-two conjecture. ω=2. This would establish the optimal possible asymptotic…
An Abelian Cayley graph is a Cayley graph of an Abelian group; its chromatic number is the least number of colors in a proper vertex coloring. Finitary Abelian Cayley graph conjecture. There exists an absolute constant c such that, for…
Let D be a digraph, and let k≥ 2 and ℓ≥ 2 be fixed integers. The parameter κ_k(D) is the maximum, over all k-vertex subsets of D, of the number of internally vertex-disjoint strong subgraphs containing that subset. Sun–Gutin–Yeo–Zhang's…
Let sc_SchubertVanishing be the decision problem asking whether a Schubert coefficient vanishes. Schubert-vanishing hardness conjecture. sc_SchubertVanishing is coNP-hard. The conjecture is presented as a consequence of the preceding…
Let p-\texttt{NPP} and u-\texttt{NPP} denote the planted and unplanted random number partitioning problems, respectively. For a fixed c>1, consider distinguishing these two models in the regime described by the hypothesis-testing problem.…
Let D be a digraph. For a digraph G, let i_D denote the problem of deciding whether G contains an induced subdivision of D. A spider is a tree obtained from disjoint directed paths by identifying one end of each path into a vertex, and C_2…
Fix d>0. Let S⊂ R^k be a symmetric semi-algebraic set defined by a P-closed formula, where P is a set of symmetric polynomials of degrees bounded by d. For each partition λvdash k, write m_i,λ(S,Q) for the multiplicity of the irreducible…
Let (X,T) be an efficiently discretizable topological dynamical system. Recall that T is topologically exact if, for every nonempty open set U⊂ X, there exists n_0∈N such that T^n_0(U)=X. A telic problem is called hard-on-average when it…
Let sc_SchubertVanishing be the decision problem asking whether a Schubert coefficient vanishes, for Schubert coefficients in the classical types A, B, C, and D. Schubert-vanishing coNP conjecture. sc_SchubertVanishing is not in coNP. The…
Let Γ be a finite core, and let Δ:= (0,1;(0,0,1),(0,1,0),(1,0,0)). A primitive positive interpretation of Δ in Γ is an interpretation using primitive positive formulas. Bulatov–Jeavons–Krokhin conjecture. If there is no primitive positive…
Let (X,f) be a finite connectivity system. Its ultrafilter width is ufw(X,f):=maxk≥ 0 | there exists a non-principal ultrafilter of order k+1 on (X,f), provided that at least one such ultrafilter exists. Connectivity-system SSE-type…
Let G be a graph, let V(G) be its vertex set, and let f(G) denote the exact minimum size of a vertex-separating tree system of G. Threshold-complexity conjecture. Determining whether f(G)=ciellog|V(G)|⌉ for a given graph G is NP-complete.…
Let H be a directed graph. The H-colouring problem asks whether an input directed graph admits a homomorphism to H. Dichotomy conjecture. The H-colouring problem is polynomial-time solvable or NP-complete. This conjecture seeks a complete…
Let F_r be a free group, and let T=T_r be the restricted set of Whitehead automorphisms described in the source. For each length l, let NMin_l⊂ F_r be the set of non-minimal elements of length l, and let NMin_l,T be the subset on which…
Let t:bN→N. For “nice” sequences of distributions P_n and Q_n on spaces Ω_n, let L_n=dP_n/dQ_n denote the likelihood ratio, and let L_n^≤ D(n) be its orthogonal projection onto polynomials of degree at most D(n) under Q_n. A function…
Given a weighted graph G=(V,E,w), where w:E→R_≥ 0, find an integral cycle basis B minimizing its total weight ∑_C∈B∑_e∈ Cw(e). Here an integral cycle basis is a basis of the integer cycle lattice of G, equivalently, a cycle basis whose…
Let bf T be a finite set of polyomino tiles on the square grid, with copies restricted to parallel translations. A tiling of [n× n] with bf T is a covering by translated tiles without overlap. The class #EXP consists of counting problems…
Let f ∈ Z[X] be a separable polynomial. For an order A, write Z_A(f) for the zero set of f in A, and let Π_f denote the problem of deciding, given an order A, whether Z_A(f) is non-empty. The complexity classes P and NPC denote…
Let a straight-line program for a polynomial in one variable be a list s_0=1, s_1=x, s_2,…,s_τ, where each s_i, for i≥ 2, is one of s_j+s_k, s_j-s_k, or s_js_k for some j,k<i. For f∈ Z[x], let τ(f) be the least length of a straight-line…