3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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'$. $\endgroup$ – D.W. Jul 14 '19 at 16:20
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 14 '19 at 16:24
  • $\begingroup$ This also can be expressed as finding affine equivalence between two Boolean functions (here, the characteristic functions of A and B). $\endgroup$ – Hyperflame Jul 17 '19 at 6:19
4
$\begingroup$

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.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you! This is great $\endgroup$ – boinkboink Jul 15 '19 at 16:49
  • $\begingroup$ It will take me some time to digest this info $\endgroup$ – boinkboink Jul 15 '19 at 17:46
  • $\begingroup$ I’m sorry if my question is trivial: The OP does not give any constraint on $A$. Why is it a linear code? $\endgroup$ – Lwins Jul 16 '19 at 0:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Jul 16 '19 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.