49 problems

Recursive upper-bound conjecture. In a $d$-dimensional setting,

Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,

Weaker dijoin decomposition conjecture. The arc set $A$ can be decomposed into a $k$-dijoin and a $(\tau-k)$-dijoin, for every $k\in\{1,\ldots,\tau-1\}$.

Let $A$ be a $\{0,1\}$-matrix whose columns each contain the same number $d\geq 2$ of $1$'s, with column vectors $v_1,\ldots,v_q$. Let $\mathcal{C}$ be the clutter associated with…

Finite exact-density tile-family conjecture. For every fixed $q$, there is a finite coordinate-symmetric family of induced templates of independence density $1/q$ such that, in eve…

Let ${\mathcal G}'(k,n)$ be the collection of graphs whose vertices are labeled by $k$-subsets of an $n$-element set, with the property that for vertices labeled by $S$ and $T$, th…

Let $k\geq 4$, and let $\delta^*(k)$ denote the optimal balanced discrepancy for the module-lattice sign-selection problem. Write $\delta^*$ for the constant value proposed by the…

MF-AOA asymptotic performance conjecture. In the limit $n\rightarrow\infty$, AMP algorithms such as the MF-AOA achieve a performance of approximately

Bollobás–Meir conjecture. For any finite set of points $X\subseteq[0,1]^k$, there exists a Hamiltonian cycle $H$ on $X$ with $S_k(H)\leq 2\cdot k^{k/2}$ if $k\neq3$, and…

Let $F_{k,m,n}(t)=\mathbb{E}(\exp(t\cdot C_{k,m,n}))$ be the moment generating function of the minimum cost $C_{k,m,n}$ of a $k$-matching in the random bipartite matching model. Ze…

Let $C_{k,m,n}$ be the minimum cost of a $k$-matching in the random bipartite matching model, and let its cumulants $\kappa_p$ be defined by … where…

Bounded-entry tree integer-programming conjecture. The integer program can be solved in polynomial time for constant $d$.

Totally $\Delta$-modular integer-program conjecture. For any constant $\Delta$, this integer program can be solved in polynomial time when $A$ is totally $\Delta$-modular.

Taillard's conjecture. For a fixed number of machines $M$,

Let a quadratic assignment problem (QAP) instance be given, and suppose that a few assignments are identified as belonging to a high-quality solution. Consider permanently fixing t…

Quadratic-logarithmic lower-bound conjecture. There exist instances of the textsc{Pebble Motion Problem on Trees} for which the length of the shortest solution sequences is

Let $G(k)$ be the length of an optimal Golomb ruler with $k$ marks. Singer-type upper-bound conjecture. For every integer $k\geq6$, … The source derives this as a consequence of th…

Bounded-degeneracy conjecture. The limit

Let $M$ be a matroid on a ground set $E$, let $\Gamma$ be an abelian group, let $\psi\colon E\to\Gamma$ be a group labeling, let $F\subseteq\Gamma$ be a finite set, and let…

Brändén–Huh's conjecture. The following conditions are equivalent:

Let $k\geq 1$ and let $d$ satisfy … A good binary tree of height $k$ is defined recursively: a height-zero tree is a single node, and for positive height at most one child-subtree…

Priestley's conjecture. $k$-ECSM admits a polynomial-time $(1+O(1/k))$-approximation algorithm.

Bounded-excess conjecture. There is a constant $c>0$ such that

Fixed-$\Delta$ tractability conjecture. There is a polynomial-time algorithm to solve any integer program of the form (IP) with a $\Delta$-modular constraint matrix.

Structured-vector optimality conjecture. The vector $\boldsymbol{v}^*$ is an optimal solution of the paper's continuous minimization problem.