Open algorithmic problems from a talk by Alon

The UCI mathematics department had a departmental colloquium today given by Noga Alon, titled “The Polynomial Method and its Algorithmic Aspects”. One part of his talk that I found very interesting was a collection of easy-to-state combinatorial problems where the existence of a solution can be proved, but there is no known efficient (polynomial time) algorithm for finding the solution:

Let $p$ be a prime number, and suppose that we are given two inputs: a sequence $A = a_{1}, a_{2}, \dots a_{k}$ of elements of $Z_{p}$ , of length $k < p$ , not necessarily distinct from each other, and a set $B$ , also consisting of $k$ elements of $Z_{p}$ , distinct but not ordered. Can we pair them up by assigning an ordering $b_{1}, b_{2}, \dots$ to the elements of $B$ so that all of the sums $a_{i} + b_{i}$ are distinct? For instance, if all of the $A$ ’s are equal, then any ordering of the $B$ ’s will work.
Let $G$ be a bipartite graph that has a perfect matching. Assign “non-degrees” to the vertices on one side of the bipartition, numbers that should not be the degree of the vertex. Can we delete some subset of the vertices on the other side, so that in the remaining graph each vertex’s degree is different from its non-degree? For instance, if the non-degrees are all zero, then $G$ itself will work (it has nonzero degree because it has a perfect matching). If the non-degrees are all non-zero, then we can delete all of the vertices on the other side of the bipartition.
Let $G$ be a planar graph with degree three at every vertex, and suppose also that each edge of $G$ has a list of three colors available to it. Can we assign colors from these lists to the edges so that each vertex touches edges of three different colors?
Let $C_{1}$ and $C_{2}$ be proper colorings of a large $d$ -dimensional grid, using $q \geq d + 2$ colors, and let $S_{1}$ and $S_{2}$ be subsets of the vertices of the grid that are far apart from each other (I am not sure how far this needs to be but it seems to be $d \pm O (1)$ or maybe $q \pm O (1)$ ). Can we find a proper coloring of the whole grid that blends between the two colorings, agreeing with each $C_{i}$ on $S_{i}$ ? This one comes from a new paper by Alon, Raimundo Briceño, Nishant Chandgotia, Alexander Magazinov, and Yinon Spinka, “Mixing properties of colourings of the $Z^{d}$ lattice”, Combinatorics, Probability and Computing 2021. Fewer colors will not always work.

In all of these cases, the answer to the existence problem is yes, but we don’t know of an efficient algorithm for finding the structure that is supposed to exist. Instead, Alon proves the existence non-constructively, through a combinatorial Nullstellensatz encoding the principle that low-degree polynomials don’t have many roots. For one-variable polynomials of degree $d$ , for instance, there cannot be more than $d$ values at which the polynomial is zero. But the degree really has to be $d$ , and not merely at most $d$ , because the degree-zero constant-zero polynomial is zero everywhere.

The analogous principle Alon uses for higher numbers of variables is the following: Let $p$ be a polynomial of degree $d$ in the variables $x_{1}, x_{2}, \dots x_{n}$ , over some field, and let $t_{i}$ be the exponents of a nonzero monomial $\prod_{i} x_{i}^{t_{i}}$ of degree $d$ in $p$ . Additionally, let $S_{i}$ be (not necessarily distinct) sets of $t_{i} + 1$ elements. Then we can choose an element $s_{i}$ in each $S_{i}$ such that $p (s_{1}, s_{2}, \dots)$ is non-zero. Alon surveys this principle and its applications in his paper “Combinatorial Nullstellensatz”, Combinatorics, Probability and Computing 1999.

The hard parts about using this method to prove existence in combinatorial problems such as the ones above are finding the right polynomial and proving that it has a nonzero coefficient at the right monomial. The problem on reordering with distinct pairwise sums, for instance, comes from Alon’s paper “Additive Latin transversals”, Israel J. Math. 2000 and uses the polynomial

\prod_{i < j} (x_{i} - x_{j}) (a_{i} + x_{i} - a_{j} - x_{j})

where each $S_{i} = B$ , the first terms in the product can only be nonzero if each $x_{i}$ is chosen to be a distinct member of $B$ , and the second terms in the product can only be nonzero if the pairwise sums are different from each other. The coefficient of the monomial $\prod x_{i}^{k - 1}$ turns out to be (up to sign) exactly $k!$ , which is nonzero modulo $p$ by the assumptions that $p$ is prime and $k < p$ . The nonzero coefficients for the other two problems are not so easy to compute: they are the permanent (number of perfect matchings) and the number of 3-edge-colorings of the given graphs. For the case of 3-edge-colorings, the fact that this number is nonzero is one of the equivalent forms of the 4-color theorem.

The general problem of constructing a nonzero solution to an instance of the combinatorial Nullstellensatz whose polynomial is described by an arithmetic circuit is (according to Alon) as hard as inverting arbitrary one-way permutations, a standard cryptographic primitive. This suggests that a polynomial-time construction algorithm does not exist; if it did exist, it would break a lot of modern cryptography. On the other hand, proving that it does not exist would also prove $P \neq NP$ . Despite this relation to standard hard problems, there’s no strong reason for believing that any of the combinatorial problems outlined above is as hard as the general case, so maybe they might still have an efficient algorithm. If so, it would probably translate into an existence proof that is substantially different than the ones we already have for these problems.

(Discuss on Mastodon)