Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let a sum of superstars be a disjunctive sum of impartial combinatorial games whose components are superstars, and let \ruleset{Paint Can} denote the corresponding game. PSPACE-completeness conjecture. A sum of superstars, and hence…
Let SchubertVanishing denote the decision problem of determining whether a Schubert coefficient vanishes. Pak and Robichaux's conjecture. The problem SchubertVanishing is textsccoNP-hard. This conjecture concerns the computational…
Let textscComputeKron be the problem of computing g(λ,μ,ν) from partitions λ,μ,ν, and let ℓ(λ) denote the number of parts of λ. Panova's conjecture. The problem textscComputeKron is in #P when restricted to ℓ(λ)=2 if and only if it is in…
For integers k and m, let APUD(k,m) denote the graph class consisting of intersection graphs of disks whose centers lie on k parallel lines, with the relevant representation restricted by parameter m. APUD recognition conjecture.…
Let G and H be graphs, and let Rem_H(G) denote the maximum number of edges in an H-free spanning subgraph of G. A graph H is a star forest if every connected component of H is a star. Alon–Shapira–Sudakov conjecture. Computing Rem_H(G) is…
Let t be a positive rational number. The decision problem scshape Min-t-Tough asks whether a graph is minimally t-tough, meaning that its toughness is at least t and deleting any edge decreases its toughness below t. Min-t-Tough complexity…
A series-parallel graph is a graph in the class of graphs obtained through series and parallel composition. The Minimum Eternal Vertex Cover problem asks for the minimum number of guards needed to perpetually defend every edge against the…
A rectangle tiling set is a finite set R of rectangles, and a simply connected region is a region in the plane without holes that is to be tiled using translated copies of rectangles from R. Pak–Yang's conjecture. There exists a set R of 3…
Let XPM denote exact perfect matching: given a graph with blue/red-colored edges and an integer k, determine whether there exists a perfect matching containing exactly k red edges. Let PM-VC-Sym denote perfect matching under vertex-color…
Consider a Turing machine using an experiment as a physical oracle through an exponential-time protocol. For infinite and unbounded precision, the relevant class is P/log*; for fixed, finite precision, the relevant class is BPP//log*.…
A tournament is an oriented graph in which every pair of distinct vertices is joined by exactly one directed arc. Given a tournament T and an integer k, the decision problem asks whether its inversion number inv(T) is exactly k. Exact…
Let P e∅ be a rational polytope in R^3. The Polytope Translation hardness conjecture. The Polytope Translation problem for rational polytopes P⊂ R^3 is NP-hard. This conjecture asks whether the known hardness result in dimension six can be…
Let W be a GOE(n) matrix, let x∈0,1^n have exactly k nonzero entries, and observe Y=λ/kxx^top+W, with 1≪ k≪ n. Exact recovery means outputting x with probability tending to 1 as n→∞. Sparse PCA runtime conjecture. For any λ in the hard…
Let K_n be the complete graph on n vertices, let Ramsey(n,n) be the symmetric binary Ramsey number, and let K_Ramsey(n,n) be the complete graph on that many vertices. Explicit-Ramsey-number avoidance conjecture. The graph Ramsey avoidance…
Let X be a set of T instances equipped with an unknown total order prec, and let C_prec be the class of threshold concepts whose positive sets are prefixes of prec (with the empty prefix included or excluded according to the model). In…
Let m be a positive integer. Height-two universality conjecture. For all sufficiently large m, there exists a poset P of height two such that e(P)=m. The source states that this conjecture would imply the coincidence-complexity result for…
A graph G has a set of pressing sequences, namely vertex orderings satisfying the pressing condition defined in the paper. The #P-hardness conjecture. Exactly counting the pressing sequences of a graph is #P-hard. The statement concerns…
For partitions λ, μ, and ν of the same integer, let g(λ,μ,ν) denote the Kronecker coefficient, and let textscKron be the problem of computing this coefficient from the binary-encoded input. Mulmuley's conjecture. textscKron∈ rm#P. The…
Let (X,T) be an efficiently discretizable topological dynamical system. A subset E⊂ X is closed when it is closed in the topology of X; sensitivity to initial conditions means that the dynamics separates sufficiently close initial points…
Let D be an oriented graph and let k be a positive integer. The underlying graph of D is the graph obtained by ignoring the orientations of its arcs. Oriented chordal hull-number conjecture. Determining whether overrightarrowhn(D)≤ k is…