Instead of directly looking for instances that fool the hierarchy, our approach
shall be to consider the following questions: How does a certificate of
acceptance for the \(\operatorname{BA}\)  hierarchy look like? Can we tell, from the shape of
such a certificate, what the limits of the hierarchy applied to AGC are? The first step of our analysis is to translate the problem of whether the \(\operatorname{BA}\)  hierarchy accepts an input into a problem having a different, multilinear nature.
Building on the framework developed in [1]}, we find that \(\operatorname{BA}\)  acceptance is implied by the existence of a family of tensors having certain special characteristics. First of all, they need to satisfy \((i)\)  a system of symmetries.
This is essentially the result of the marginality constraints that are enforced by all “lift-and-project” hierarchies such as the \(\operatorname{BLP}\) , \(\operatorname{AIP}\) , and Lasserre \(\operatorname{SDP}\)  hierarchies [2]}, and is common to all algorithmic hierarchies studied in [1]} through the tensor approach.
There is, however, a feature that is typical of the \(\operatorname{BA}\)  hierarchy.
Not only does \(\operatorname{BA}\)  require that both a linear program and a system of Diophantine equations have a solution; it also requires that any variable that is assigned zero weight by the former should be also assigned zero weight by the latter. This refinement condition of the relaxation introduced in [4]} blends together the consistency-enforcing and linear-equation-solving techniques, to produce an algorithm that, as discussed above, is provably strictly stronger than both. The translation of the refinement condition into the multilinear framework is \((ii)\)  a hollowness requirement: Each tensor certifying \(\operatorname{BA}\)  acceptance needs to be hollow; i.e., it needs to contain zeros in certain prescribed locations. Summarising, the original problem has now become the following:
