Given a subset of of the hypercube and an affine transform of it, find the affine map

This is a follow up to this resolved question. Suppose we are given a set of bitvectors $$A\subseteq\mathbb{F}_2^d$$ and an invertible affine transformed copy of it $$B=\{Mx + s\mid x\in A\}$$ for some full rank $$M\in\mathbb{F}_2^{d\times d}$$ and $$s\in\mathbb{F}_2^d$$.

Given $$A$$ and $$B$$ what are the randomized and quantum complexities of finding an $$M$$ and an $$s$$ so that $$MA + s = B$$ (let us assume SETH for the purposes of this post)?

Does this connect to any problems studied in tcs?

• You can ignore $s$ if it helps. If you can find $M$ such that $MA=B$, you can solve your problem, too. In particular, replace each vector $x=(x_1,\dots,x_d)$ with $x'=(x_1,\dots,x_d,1)$, find $M$ such that $M'A'=B$, and then you'll be able to reconstruct $M,s$ such that $MA+s=B$, by letting $M$ be the first $d$ columns of $M'$ and $s$ the last column of $M'$.
– D.W.
Jul 14, 2019 at 16:20
• A possible approach is to put $A$ into a $d\times n$ matrix $A^*$ (with each vector in $A$ into a column of $A^*$), put $B$ into a $d \times n$ matrix $B^*$, and then try to find a permutation of the coordinates that maps $\text{Ker}\; A^*$ to $\text{Ker}\; B^*$. In particular, you can try to count the number of entries of weight $w$ in $\text{Ker}\; A^*$ and $\text{Ker}\; B^*$ and use that to try to match them up. Probably still exponential-time in the worst case.
– D.W.
Jul 14, 2019 at 16:24
• This also can be expressed as finding affine equivalence between two Boolean functions (here, the characteristic functions of A and B). Jul 17, 2019 at 6:19

From D.W.'s comment, we see that your problem is equivalent to the same problem with $$s=0$$ (and with $$d$$ only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem over $$\mathbb{F}_2$$, just phrased slightly differently. (Usually CodeEq is phrased as "you have two $$d \times n$$ generator matrices of linear codes, is there a permutation of the $$n$$ columns which makes the two generator matrices have the same row-span?" In your case, the action by $$GL(d,2)$$ is the action which preserves the row-span, and the fact that you are only interested in a set of vectors means you essentially have an action of $$S_n$$ on the columns.)

Here's what's known about its complexity:

• This problem is at least as hard as Graph Isomorphism (essentially goes back to Luks '93 "Permutation groups and polynomial-time computation", see Miyazaki, though it is often cited to Petrank-Roth '97)
• As with GI, it is in $$\mathsf{NP} \cap \mathsf{coAM} \cap \mathsf{SZK}$$, by essentially the same proof as for GI.
• It's no harder than Tensor Isomorphism [GQ19]
• The best known worst-case upper bound is $$2^{O(n)}$$ (due to Babai, cf. [BCGQ11])
• There is an algorithm by Sendrier 2000 that may work well in practice, depending on what kinds of codes you are looking at.
• Thank you! This is great Jul 15, 2019 at 16:49
• It will take me some time to digest this info Jul 15, 2019 at 17:46
• I’m sorry if my question is trivial: The OP does not give any constraint on $A$. Why is it a linear code? Jul 16, 2019 at 0:34
• @Lwins: $A$ itself need not be a linear code. We take the set of vectors $A \subseteq \mathbb{F}_2^d$, $|A|=n$, and use them as the columns of a matrix. The code is then the row-span of that matrix, which is fine in this problem since the OQ was interested in invertible change of basis on $\mathbb{F}_2^d$, which preserves the row-span. Jul 16, 2019 at 6:24