Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A full 2× n board is a board with two rows and n columns, initially containing a button in every cell; the board has C=2 colors when its buttons use two colors. Here, s denotes a constant independent of n. Two-row Buttons & Scissors…
Let β ∈ [-1,∞) and γ>0. For each n∈ N, set N=⌈ n/γ⌉, and let P and Q be the spiked Wishart distributions defined by the null model Q with independent samples y_i~ N( 0, I_n) and the planted model P obtained by sampling x~Unif(±1^n) and…
A 2-hypergraph is a hypergraph whose hyperedges have size two, and PL realizability in R^d means realizability by a piecewise-linear representation in R^d. The PL realizability conjecture. (a) Deciding whether a 2-hypergraph is PL…
Let G be a graph and let A be the achievement graph, with no precolored red or green edges, denoted by (G,A,,). Unrestricted graph Ramsey-game conjecture. Graph Ramsey games played on (G,A,,) are bf PSPACE-complete. The conjecture concerns…
Consider asymptotic hypothesis-testing problems between probability measures mathbb P and mathbb Q. For degree at most D, define the low-degree advantage by Adv_≤ D(fracd Pd Q):=sup_f∈ P_Dfrac E_ P[f]√ E_ Q[f^2]. Here mathcal P_D is the…
Let P be a finite poset with fixed prescribed values represented by z, c, and let N_ z, c(P) denote the number of linear extensions satisfying those prescriptions. Constrained linear-extension counting conjecture. For every fixed integer…
A relational structure T is a structure consisting of a domain together with relations of prescribed names and arities. For a fixed relational structure T, textscCsp(T) is the decision problem whose instances are relational structures S…
Let ComputeKron be the problem of computing g(λ,μ,ν) from partitions λ,μ,ν. Write ℓ(λ) for the number of parts of λ, and let (n^d) denote the rectangular partition with d parts equal to n. Panova's restricted-case conjecture. The following…
Let G(n,a/n,b/n) be the planted partition model with k communities, where a>b. Let c(k) be a threshold depending only on k. Decelle–Krzakala–Moore–Zdeborová's Potts-model conjecture. For any k, there exists c(k) such that…
Let t: N → N. Consider a “natural” high-dimensional testing problem specified by distributions P_N and Q_N on an observation space Ω_N, and let L_N denote the corresponding likelihood ratio, with |L_N^≤ D(N)| its degree-D(N) low-degree…
Let ν denote the paper's robustness measure for systems with structured uncertainties, and let arbitrary precision mean that the computed value can be made to have any prescribed accuracy. Polynomial-time computation conjecture. There…
For f∈Z[T], define τ(f) as the least k for which f occurs in a sequence beginning with f_-1(T)=1 and f_0(T)=T, with each later polynomial obtained from two earlier ones by addition, subtraction, or multiplication. Let Z(f) be the number of…
Let D and D' be digraphs. For a digraph G, let i_D (respectively, i'_D) denote the corresponding induced-subdivision detection problem. Say that D is an induced subdigraph of D' if D' contains a vertex-induced copy of D. Monotonicity…
A strong geodetic set of a graph is a vertex set satisfying the strong geodetic property, and the associated decision problem asks whether a graph has such a set of size at most a prescribed bound. A complete multipartite graph is a graph…
Assume the unique games conjecture and consider the dynamical systems associated with unique games instances, together with their invariant-measure scaling properties. Turing-machine limitation conjecture. If the unique games conjecture is…
Let φ be a univariate polynomial closure property of #P, and say that it relativizes when the corresponding closure holds for every oracle version #P^A. Univariate binomial basis conjecture. Every univariate polynomial closure property of…
Let H be a finite digraph, viewed as a relational structure, and let CSP(H) ask whether a finite input digraph admits a homomorphism to H. Digraph CSP dichotomy conjecture. CSP(H) is solvable in polynomial time or NP-complete. Feder and…
Let G be a finite solvable group. The problems textscEQN-SAT(G) and textscEQN-ID(G) ask, respectively, whether an equation over G has a satisfying assignment and whether it is an identity over all assignments. Quasipolynomial-time…
Let cmu be a union of connected conjunctive queries over a signature ctau, let cDelta_cmu be the associated valued structure, and let cmathfrak A be a finitely bounded homogeneous expansion of cmathfrak C_cmu. Let (0,1;OIT) denote the…
For a set T of trees, a graph is ( T∪K_k)-free if it contains no member of T and no copy of K_k as an induced subgraph. Sandwich-problem hardness conjecture. For every positive integer k≥ 4 and every possibly infinite set T of non-star…