We prove that the \(\operatorname{BA}\)  hierarchy does not solve AGC.
This substantially extends the known results on non-solvability of AGC by the two weaker Sherali-Adams LP and \(\operatorname{AIP}\)  hierarchies separately.
Ruling out the first level of the \(\operatorname{BA}\)  hierarchy is trivial
using the characterisation from [1]}, while the task is significantly more challenging for higher levels.
The core of our proof is geometric. Using the framework recently developed by Ciardo and Živný in [2]} to study algorithmic hierarchies, we reduce the problem of finding a “fooling instance” for the \(\operatorname{BA}\)  hierarchy applied to AGC to the following geometric problem: building a high-dimensional integral tensor whose projections onto hyperplanes of fixed dimension are equal up to reflection (i.e., up to permutation of the tensor modes) and satisfy a sparsity condition, which dictates that certain entries of the tensor should be set to zero. The main technical result of this work is a constructive proof of the existence of tensors having these features.
An active research trend in combinatorial matrix theory investigates the conditions for the existence of matrices (i.e., 2-dimensional tensors) over a certain domain having prescribed row- and column-sums (i.e., 1-dimensional projections) and a fixed pattern, i.e., a fixed set of entries allowed (or required) to be nonzero. Examples include 0-1 matrices with zero trace (i.e., adjacency matrices of digraphs) [3]}, with at most one fixed zero in each column [4]}, or with a fixed zero block [5]},
real matrices with a fixed pattern [6]}, and
integral matrices with fixed lower and upper bounds on each entry [7]}; see also related work in [8]}, [9]}, [10]}.
We believe that our work will stimulate further progress within that trend since, for the first time to our best knowledge, it extends the investigation from matrices to tensors of arbitrary dimension.
