Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
The k-general d-position problem takes as input a graph G, integers k≥ 2 and d≥ 1, and a positive integer r, and asks whether gp^k_d(G) is greater than r. Complexity conjecture. The k-general d-position problem is NP-complete. This…
Let T be a graph, let F be a family of graphs such that no F∈F is a subgraph of a blow-up of T, and let ε>0. For a graph G on n vertices, write ex(G,T,F) for the maximum number of copies of T in an F-free subgraph of G.…
A multihitting clause-set is a generalised clause-set in which the associated conflict structure satisfies the multihitting condition. Satisfiability asks whether such a clause-set has a satisfying assignment. Multihitting satisfiability…
Let G=(V,E) be a graph on n vertices. For t∈N and β>0, call G (β,t)-intersecting if, for every t subsets S_1,…,S_t⊆ V of size β n and every t bijections π_i:S_i→[β n], there exist j,k∈[β n] such that (π_i^-1(j),π_i^-1(k))∈ E for every…
Let C ⊇ P be a standard complexity class, such as P, NP, PSPACE, or EXP. Consider the semiring formed by the p-cardinalities of languages in C, together with the corresponding semiring of equivalence classes of p-cardinalities.…
Let p∈(0,1) be constant. For each n, let A_n:G_n→0,1 be a randomized polynomial-time algorithm, and let k_n be a sequence of positive integers satisfying limsup_n→∞log_n k_n<1/2. For the planted clique detection problem, with null…
A polyomino is a finite union of edge-connected unit squares in the plane. It is convex if every row and every column has at most one connected component. The minimal domination problem asks for the smallest attacking or non-attacking…
Let a Gabidulin code be given together with a received word. A received word is a deep hole if its distance from the code equals the covering radius. NP-hardness conjecture. Deciding whether a received word is a deep hole of the Gabidulin…
Let (X_n,P) be a sequence of CLVMs, giving rise to sequences of measures P_n and Q_n on Ω^N, where N=N(n). Let Adv_≤ D(X_n,P) denote the low-degree advantage, and let strong detection mean distinguishing the two measures with the…
Let Γ be a valued structure with finite signature such that Aut(Γ)=Aut(B) for some reduct B of a countable finitely bounded homogeneous structure. A pp-construction is the primitive-positive construction notion used in the paper, and…
A physical theory is called “realistic” when it satisfies the intended assumptions described in the paper, and an experiment is used as a physical oracle by a Turing machine through a protocol whose query specifies the experimental…
Let A be a finite relational structure, and let CSP(A) denote the problem of deciding whether a finite input structure has a homomorphism to A. A core is the canonical core template referred to in the source, and a Taylor polymorphism is…
Let H be a finite structure with finite relational signature, and let its polymorphisms be the operations preserving the relations of H. A Noname chain is the chain defined in Section~. Egri–Larose–Tesson's conjecture. If the polymorphisms…
Let minnonmer:N→N denote the minimum variable-degree function for minimally unsatisfiable clause-sets indexed by deficiency, and let potprec(vec a) denote the functions represented by finite tuples vec a. Computability conjecture. The…
Let G_n be the set of graphs with n vertices, and let G(n,1/2) and G(n,1/2,k,q) denote the null and alternative graph distributions, respectively. For a sequence k=k_n satisfying k≤ n^β for some 0<β<1/2, let q∈(1/2,1], and consider tests…
Let X have prior distribution P_0, and consider the rank-one symmetric matrix estimation model Y_i,j=√λ/nX_iX_j+Z_i,j, where Z_i,j are standard Gaussian noises. Assume E_P_0[X]=0 and E_P_0[X^2]=1. Let λ_c be the critical value defined by…
Let Y^* denote the true support matrix in the submatrix localization model. Assume μ≤ 1, n_L=n_R=n, K_L=K_R=K, and K≥ c_1log n. Submatrix localization computational-hardness conjecture. For every constant ε>0, no algorithm with running…
Let Λ∈(0,1) be a peak. A Single-Peaked Jump Schelling Game and a Single-Peaked Swap Schelling Game are instances of the respective models, and NE denotes a Nash equilibrium. Equilibrium-existence complexity conjecture. For both the…
Let (H,Π) be a connected signed graph. An s-core of (H,Π) is a signed graph obtained by the standard core reduction, equivalently characterized by the property that every s-homomorphism from it to itself is an s-automorphism. Let…
A graph G is planar if it can be drawn in the plane without edge crossings. For a graph class H, the H-square-root problem asks whether a given graph has a square root belonging to H. Planar square-root conjecture. The H-square-root…