66 problems
Given a finite graph with an edge-colouring and no alternating cycle, and given prescribed ordered pairs of vertices, dec…
Does there exist a deterministic algorithm which, given a finite field and a polynomial of degree , outputs all elements …
For a permutation , let be the minimum number of transpositions whose product sends to the identity permutation . Define the transposition…
For every integer and every planar graph , there exists a constant such that every graph with no induced subgraph isomorphic to and with no ind…
Given a directed graph , vertices , and an integer , construct a sensitivity oracle that, after preprocessing , answers exactly for every set of at m…
, if is an -vertex graph embeddable on an orientable surface of genus and has maximum degree , then…
For a pivoting rule and dimension , let denote the supremum, over all nonsingular matrices , of the ratio between the large…
This entry tracks Gartland–Lokshtanov conjectures on induced matching treewidth. It advances the structural classification behind algorithms on graph classes with bounded induced m…
This entry tracks Random-reshuffling-versus-SGD open question. It addresses a longstanding theory–practice question about random reshuffling’s empirical advantage. Latest developme…
This entry tracks Harvey–Hittmeir question on deterministic integer-root finding. The conditional result reaches input-size complexity up to logarithmic factors, with an unconditio…
Let be a simple graph, directed or undirected, with positive real-valued edge weights, and let . When the graph is accessed through vertex and incident-edge que…
Given a semicomplete digraph and distinct vertices , determine a longest directed -path. Given a locally semicomplete digraph and distinct vertices…
Determine whether there exist universal constants and a polynomial-time online signing algorithm such that, for every dimension and every finite horizon , when…
Let be a graph and let be a nonnegative integer. Consider the serial algorithm and parallel algorithm for constructing the -skeleta of the clique complex of describe…
Let be a clause-set with deficiency surplus . Write for its minimum variable-degree and for…
Hochbaum–Nishizeki–Shmoys conjecture. There exists a polynomial-time algorithm that finds a proper edge-coloring of every multigraph using col…
Fix a code . Given a code of length , polynomial-time minor-containment conjecture. It is decidable in time polynomial in whether …
Let denote the total cost of the Quick-Find-Weighted algorithm through its first mergers, and let denote convergence…
Let be a sequence generated by the CCL procedure, and let be the fast forward permutation coded by this sequence. Choose uniformly…
Let be a planar graph with vertices. A balanced four-coloring is a proper -coloring in which each color is used on fewer than vertices. Linear-time balanced…
Linear-time certifying algorithm conjecture. For every fixed positive integer , there is a certifying algorithm that runs in time
Let an equitable -coloring be a proper -coloring whose color classes have sizes differing by at most one, and let denote the degree of a vertex . Kierstead-Kostochk…
Let be a string graph, let be its size, and let and denote the parameters used by the source. An -coloring is a coloring with…
Universal termination conjecture. There exist universal functions and such that, when the proposed algorithm is guided by this pair of functions, it ter…
Let be points and let be edges of a convex hull, with each point matched to one edge and the resulting triangles considered as in the preceding he…