Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G_n~PDS(n,k_n,p_n,q_n), where the planted support has size k_n. Exact recovery means outputting the planted support. If k_n=ω(√ n) and limsup_n→∞log_nk_n^2(p_n-q_n)^2/nq_n(1-q_n)<0, the planted dense subgraph recovery conjecture. No…
Let d≥ 4 be fixed. An f-vector is a vector recording the face numbers of a d-polytope, here written as f=(1,f_0,…,f_d-1). NP-hardness conjecture. It is NP-hard to decide if a given N-bit vector f=(1,f_0,…,f_d-1) of positive integers is the…
Let F be a fixed strict digraph. An F-subdivision is a digraph obtained from F by replacing each arc ab with a directed (a,b)-path; the associated problem asks whether an input digraph D contains an F-subdivision as a subdigraph.…
An edge-colored complete graph is a complete graph whose edges are assigned colors, and a PC Hamilton cycle is a spanning cycle whose consecutive edges have distinct colors. Gutin–Kim conjecture. It is polynomial-time checkable whether an…
Let K_n be the complete graph on n vertices, let A be the achievement graph, and let E^r and E^g be the precolored red and green edge sets. Achievement-game tractability conjecture. Graph Ramsey achievement games played on (K_n,A,E^r,E^g)…
A coherent configuration is a finite set equipped with a partition of its ordered pairs into basis relations; it is commutative when its adjacency algebra is commutative. A coherent configuration realizes the matrix multiplication tensor ⟨…
Let G be a finite group, let L be a link, and define H_L(G)=|Hom(π_1(S^3∖ L),G)|. An FPRAS is a fully polynomial randomized approximation scheme, and a group is solvable if it has a finite derived series terminating in the trivial group.…
Let P be a polytope, let i be a face dimension, and let H be a hyperplane. For a central hyperplane H_0, write H_0^+ for one of the associated halfspaces. Hardness conjecture. (i) It is NP-hard to find a hyperplane H which maximizes the…
Let a graph be well-covered when all its maximal independent sets have the same cardinality; a maximum independent set is an independent set of cardinality α(G). The recognition complexity claim. It is NP-complete to recognize well-covered…
Fix a constant p∈(0,1). Let E be a fixed known partition of [n] into k_n equally sized subsets, and under the alternative choose exactly one planted clique vertex uniformly from each part. Let ktextsc-PC_D(n,k_n,p) denote the resulting…
Let p and t be fixed, and let f∈Z[x_1] be an input t-nomial, meaning a univariate integer polynomial with at most t monomial terms. Root-counting conjecture. There is a polynomial-time algorithm that counts the roots of f in Q_p. This…
Let (X,G) follow the same stochastic block model as in the achievability conjecture, with SNR=(a-b)^2/k(a+(k-1)b). Decelle et al.'s computational impossibility conjecture. Irrespective of k, if SNR<1, it is impossible to detect communities…
Let G) be a finitely generated group and let fcolon N→N. A filling length function of a finitely presentable group is the function measuring the maximal length occurring during fillings of null-homotopic words. A nondeterministic symmetric…
Let G be a graph with maximum degree Delta(G) ≤ 4, let λ ≥ 2, and let H be a backbone. For an integer l, BBC_λ(G,H) ≤ l denotes the λ-backbone coloring problem with at most l colors. Backbone coloring complexity conjecture. For any l ≥ λ+2…
Let T be the theory used to define H', and let H' be the collection of dense sets of true T-unprovable sentences described in the source. Given a nondeterministic Turing machine M accepting coTHEOREMS, consider inputs ⟨φ_i,1^t⟩ with i in a…
Let D be a connected plane digraph and let k be an integer. The Directed Plane Strong Connectivity Augmentation problem asks whether there is a set X⊆ V(D)^2 with |X|≤ k such that D+X is strongly connected, directed, and plane for the same…
Let k≥ 3, let F be a k-uniform hypergraph, and let G be an input k-uniform hypergraph. Write rem_F(G) for the minimum number of edges that must be removed from G to make it F-free. A matching is a hypergraph whose edges are pairwise…
Let A be a reduct of a finitely bounded homogeneous structure, and let B be a finite structure. The restricted constraint satisfaction problem RCSP( A, B) has A as its infinite template and B as its finite restriction. Let K_3 be the…
Let opcatSA be the category whose objects are embedded semi-algebraic sets and whose morphisms are restrictions of polynomial mappings. Let cA consist of scalar multiplication, addition, multiplication, the inclusion [0,∞)hookrightarrowR,…
Let k≥ 3 be fixed, let G be a graph, and let ℓ≥ 2 be an integer. Li's conjecture. Deciding whether κ_k(G)≥ℓ is NP-complete. The source states this conjecture after noting that the corresponding problem for fixed k≥ 4 is known and that the…