Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G=(V ∪ H,D) be a factor analysis graph. M-identifiability and extended M-identifiability are the two identifiability properties defined by the matching criterion and the extended matching criterion, respectively. NP-completeness…
Let k and r be positive integers. The problem \textsc{k^thPower of a Graph With Girth r} asks, given a graph G, whether there exists a graph H of girth r such that G=H^k. Higher-power girth conjecture. The problem \textsc{k^thPower of a…
Let μ be a union of connected conjunctive queries over the signature τ, and let σ⊆τ. Write Γ:=Γ_μ,σ for the associated valued structure. A fractional polymorphism of arity ℓ is a probability distribution on ℓ-ary operations satisfying the…
A 3-SAT formula is called satisfiable if all its clauses can be satisfied, and it has at most a 1-ε fraction of satisfiable clauses if no assignment satisfies more than that fraction. Here n denotes the number of clauses. Gap-ETH. There…
Let G be a graph on n vertices with maximum degree Δ, and consider the fixed-magnetization Ising model with inverse temperature β and magnetization parameter η. The Kawasaki dynamics has two versions: local flip dynamics, proposing swaps…
Fix a positive integer r. The r^th Stable Divisorial Gonality problem asks whether a graph has stable divisorial gonality at most a given integer. Stable divisorial gonality conjecture. The r^th Stable Divisorial Gonality problem is…
For the Game of Life, consider finite-support Gardens of Eden and rectangular orphans, with the encodings specified in the paper and polynomial-time many-one reductions. Co-NP-completeness conjecture. Finite-support Gardens of Eden and…
Let G be a graph, and let APUD(1,1) denote the corresponding graph class of restricted disk intersection graphs. APUD(1,1) recognition conjecture. Given a graph G, it can be determined whether G∈APUD(1,1) in polynomial time. The preceding…
Let P_n and Q_n denote a sequence of probability measures with sample space R^n^k, where k=O(1). Suppose that every polynomial f of degree O(log n) satisfying E_Q_n f^2=1 is bounded under P_n with high probability as n→∞, and that some…
For graphs G and H, write G→ H when there is a graph homomorphism from G to H. The promise constraint satisfaction problem PCSP(G,H) asks whether an input graph maps to G or does not map to H. The PCSP hardness conjecture. PCSP(G,H) is…
Let the word problem for 3-cells of Gray categories be the problem of deciding whether two such cells are equal, and likewise let the word problem for cells of braided monoidal categories be the problem of deciding whether two such cells…
Fix a constant p∈(0,1). Let n_t and k_t be increasing sequences of positive integers such that k_t=o(√n_t) and k_t divides n_t, and let A_t:G_n_t→0,1 be a sequence of randomized polynomial-time algorithms. Under H_0, G is sampled from the…
Let G=(V,E) be a simple graph, directed or undirected, with positive real-valued edge weights, and let s,t∈ V. When the graph is accessed through vertex and incident-edge queries, is bidirectional Dijkstra instance-optimal for computing…
Let G be a graph, and for p≥ 1 let mu^(p)(G) denote its Laplacian p-spectral radius. Consider the computational problem of finding mu^(p)(G) from the input graph G. Computational monotonicity conjecture. If q>p≥ 1, then finding mu^(p)(G)…
Given a finite simple unweighted graph G=(V,E), decide whether the standard Goemans–Williamson semidefinite relaxation of Max-Cut has the same optimal value as the integer Max-Cut problem; equivalently, decide whether max_x∈±1^V1/4∑_i,j∈…
For an integer ell with ℓ≥ 3, let q=e^π i/ℓ, and let J_L(q^2) denote the Jones polynomial of a link L evaluated at q^2. An FPRAS is a fully polynomial randomized approximation scheme, and RP and NP are the standard randomized and…
Let n be a positive integer and let Q be a set of k queens placed on an n× n chessboard. For a nonnegative integer l, the minimal chessboard domination queen completion problem asks whether there is a set Q' of size k+l such that Q⊂ Q' and…
Let (Γ,Ω) be a quiver, let α∈Δ_+ be a dimension vector, and let M_α=∑_v→ wn_vn_w. A Schur vector is a dimension vector for which the corresponding representations have the Schur property. The problem INDEC[x_1,…,x_M_α] asks whether values…
A continuous-time system with switching uncertainty consists of a system whose uncertain matrix may switch among a given set of matrices. The fixed-uncertainty reduction uses the matrices constructed in Corollary; these matrices are…
Let Γ be a finite constraint language with all constants. Its polymorphism clone Pol(Γ) has the polynomially generated powers (PGP) property if, for some polynomial p, every power D^n has a generating subset of size at most p(n) under…