149 problems

Tyszka's conjecture. There exists an integer $\delta\geq 9$ such that

Let $G$ be a loopless multigraph, with maximum degree $\Delta(G)$, and define … A $\max\{\Delta(G)+1,\Gamma(G)\}$-edge-coloring assigns at most that many colors to the edges of $G$…

Krattenthaler–Müller's two-row formula conjecture. The average case complexity is

Let $F$ be a clause-set with deficiency surplus $\operatorname{\sigma}(F) \ge 1$. Write $\mu\\!\operatorname{vd}(F)$ for its minimum variable-degree and $\operatorname{nM}(k)$ for…

Let $n$ be an integer with $n\ge 2$. For a braid $\beta\in \operatorname{Br}(n)$, let $(c_m)_{m\ge 0}$ be the sequence produced by the stated computation and let $h(\beta)$ denote…

Let $P\subset\mathbb{R}^d$ be a rational polytope, and write $i_P(t)=\#(tP\cap\mathbb{Z}^d)$ for its Ehrhart quasi-polynomial. For fixed $d$, the minimum Ehrhart period conjecture.…

Let $C^{QFW}_{n,m}$ denote the total cost of the Quick-Find-Weighted algorithm through its first $m$ mergers, and let $\build{\longrightarrow }{}_{\mathcal L_2}$ denote convergence…

Let a linear list contain items that are accessed sequentially by a request sequence, and let the search cost be the number of items examined before the requested item is located.…

Let $n$ denote the size parameter of the input plane graph, and consider the embedding algorithms developed in the paper for producing pseudo-triangulation embeddings. The near-lin…

Main conjecture. For every $n>2$ there exists a constant $c(n)\geqslant 1$ such that for all braid words $w$ we have

Quasi-geodesic conjecture. The output braid words are quasi-geodesics in the Cayley graph.

Surface-braid efficiency conjecture. In this setting as well, the generalized algorithm is efficient in the sense above.

Efficiency conjecture. The relaxation algorithm is quadratic-time in the length of the input braid, and the length of its output braid is bounded linearly by the length of the inpu…

Polynomial-time conjugacy algorithm conjecture. There is an algorithmic solution to the conjugacy problem in $B_n$, using the combinatorial approach described in this paper, whose…

Fix a code ${\mathcal M}$. Given a code ${\mathcal C}$ of length $n$, polynomial-time minor-containment conjecture. It is decidable in time polynomial in $n$ whether ${\mathcal C}$…

Let $(a_0,a_1,\dots,a_l)$ be a sequence generated by the CCL procedure, and let $\pi$ be the fast forward permutation coded by this sequence. Choose $x\in\{0,\dots,N-1\}$ uniformly…

Greedy common-superstring conjecture. Greedy produces a common superstring $t'$ of length at most $2s$.

Let $G$ be a planar graph with $n\geq 3$ vertices. A balanced four-coloring is a proper $4$-coloring in which each color is used on fewer than $n/2$ vertices. Linear-time balanced…

Linear-time certifying algorithm conjecture. For every fixed positive integer $k$, there is a certifying algorithm that runs in time

Subdivided-sweep conjecture. There is a faster way to compute all cokernels of $M_{\leq g}$ for $g \in G$ in one sweep, with runtime in $\mathcal{O}(dn^3)$, rather than calling the…

Komlós' conjecture. The quantity $\kappa_n$ is bounded by an absolute constant independent of $n$, equivalently $\kappa_n=O(1)$. This is a central conjecture in discrepancy theory.…

Let $\overline{I_n}$ be the burnt pancake stack whose pancakes are in increasing order by size, with every burnt side facing up, and let $g(n)$ be the minimum number of flips neede…

Consider the discrepancy problem discussed in the source, for which Spencer's theorem guarantees the existence of a signing with the required discrepancy bounds. Spencer's conjectu…

Critical-tournament finiteness conjecture. For every $k\in\mathbb{N}$, there is a finite number of $k$-critical tournaments.

Let $S,T\subseteq\mathbb{Z}^{+}$ satisfy all the requirements of the strong $(\alpha,\beta)$-Divisor Conjecture, including the $n$-divisor property for their pairwise differences.…