Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let GninR^m× n have independent standard-normal entries. For constraint density α=lim_n→∞m/n and κ∈R_+, consider the statistical SBP S(G,κ,α). Define its algorithmic threshold by α_a(κ)=maxα | lim_n→∞P( S(G,κ,α) is solvable in polynomial…
Let S be a closed, discrete-time stochastic system over a state space X, and let its memory be M=M(S)=sup_tsup_μ I_X_t~μ(X_t;X_t+1), where the inner supremum ranges over all distributions μ on X and I(X_t;X_t+1) denotes Shannon mutual…
Let g be a normal-form game. A game is degenerate if it has a non-isolated set of Nash equilibria, and a dynamical system is of Type III as defined in the paper. Computational hardness conjecture. The computational task of finding, from…
Let G be a primitive k-out graph, meaning a finite directed graph in which every vertex has out-degree k and whose associated transition structure is primitive. Let C(G) be the set of colorings of G, and define #NSC(G):=|χ∈ C(G):χ(G) is…
Let x_0,x_1,y_0∈R_c∩[0,+∞) and consider the initial-boundary value problems and solution operators described in Theorems 1 and 2, including the stated polynomial-time computability and support conditions on the data. #P-completeness…
Let prescriptExtΦ^ℓ and prescriptExtΨ^ℓ denote the extrapolated fine- and coarse-level quantities at level ℓ. Extrapolated multilevel computational-work conjecture. The computational work required for one realization satisfies…
Let QS5 be the quantified modal logic QS5, and consider its fragment using two individual variables and a single unary predicate letter. Decidability conjecture. The fragment of QS5 in the language with two individual variables and a…
Let φ be a multivariate polynomial closure property of #P, meaning that applying φ to polynomially many #P functions yields a function in the indicated class. A closure property relativizes if the corresponding closure holds for every…
Let λ(n) be any family of Young diagrams, where the depth of λ(n) is the number of rows in the diagram. Assume that, for some constant δ>0, the depth is n-n^δ. Immanant hardness conjecture. Then Imm_λ(n) is #P-hard. Equivalently, this…
Consider the Builder/Blocker games denoted by the B-game and B'-game, together with their decision versions. Klavžar–Tian–Tuite's conjecture. The decision versions of the B- and B'-games are PSPACE-complete. The complexity of these…
Let n, d, and K be positive integers with d≥ K, and let Δ_* denote the separation parameter for the Gaussian-mixture clustering model. Write agtrsim_log b when a is at least b up to polylogarithmic factors. Polynomial-time clustering…
Let S_w denote the Schubert polynomial indexed by a permutation w∈ S_∞, and define the Schubert coefficients by S_uS_v=∑_w∈ S_∞c^w_u,vS_w. Writing sc_Schubert for the function that computes c^w_u,v, Schubert-coefficient hardness…
Let X have prior distribution P_0, and consider the symmetric rank-one matrix estimation model with signal-to-noise parameter λ. For η>0, define q^0_η=η, q^t+1_η=E_P_0[X^2]-mmse(λ q^t_η), and set widetilde q=lim_η→0lim_t→∞q^t_η. Here mmse…
Let H be the Hilbert space underlying the compact convex set considered, and let P denote the optimal runtime complexity of its projection operator, while L(0) denotes the optimal runtime complexity of exact linear minimization.…
Let the hermitian rank of a generalised clause-set be its rank under the hermitian conflict-matrix framework. Bounded-hermitian-rank satisfiability conjecture. Satisfiability decision for generalised clause-sets can be done in polynomial…
For integers k≥ l≥ 3, PCSP(K_l,K_k) is the promise problem of coloring a graph with k colors under the promise that it is l-colorable. Promise-coloring hardness conjecture. For every k≥ l≥ 3, the promise problem PCSP(K_l,K_k) is NP-hard.…
Let Λ be a lattice of dimension d, and let λ_1(Λ) denote the ℓ_2-norm of its shortest nonzero vector. In the promise problem GapSVP, given a lattice Λ and t∈R, one must distinguish λ_1(Λ)<t from λ_1(Λ)≥ α(d)t. Quantum GapSVP hardness…
Let D-uniform hypergraphs on the vertex set [N] be hypergraphs whose hyperedges are incident on D vertices. Under the null model, let G~G_D(N,p), where each hyperedge is included independently with probability p. Under the planted model,…
Let 1in3 and checkC^+ be the finite relational templates used in the paper, with a homomorphism 1in3→checkC^+. The associated promise constraint satisfaction problem is PCSP(1in3,checkC^+). checkC^+ hardness conjecture. PCSP(1in3,checkC^+)…
For a matroid presented succinctly, let EqualitySY_0 denote the decision problem asking whether equality holds in the k=0 Stanley--Yan inequality. EqualitySY coNP-completeness conjecture. EqualitySY_0 is coNP-complete for binary and for…