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

<p>Here's what's known about its complexity:</p>

<ul>
<li>This problem is at least as hard as Graph Isomorphism (essentially goes back to Luks '93 "Permutation groups and polynomial-time computation", see <a href="https://groups.google.com/forum/#!msg/sci.math.research/puZxGj9HXKI/CeyH2yyyNFUJ" rel="noreferrer">Miyazaki</a>, though it is often cited to <a href="http://dx.doi.org/10.1109/18.623157" rel="noreferrer">Petrank-Roth '97</a>)</li>
<li>As with GI, it is in <span class="math-container">$\mathsf{NP} \cap \mathsf{coAM} \cap \mathsf{SZK}$</span>, by essentially the same proof as for GI.</li>
<li>It's no harder than Tensor Isomorphism [<a href="https://arxiv.org/abs/1907.00309" rel="noreferrer">GQ19</a>]</li>
<li>The best known worst-case upper bound is <span class="math-container">$2^{O(n)}$</span> (due to Babai, cf. [<a href="http://dx.doi.org/10.1137/1.9781611973082.107" rel="noreferrer">BCGQ11</a>])</li>
<li>There is an algorithm by <a href="http://dx.doi.org/10.1109/18.850662" rel="noreferrer">Sendrier 2000</a> that may work well in practice, depending on what kinds of codes you are looking at.</li>
</ul>

CC BY-SA 4.0
2019-07-15T16:49:28.720Z
Thank you! This is great
boinkboink
CC BY-SA 4.0
2019-07-15T17:46:08.057Z
It will take me some time to digest this info
boinkboink
CC BY-SA 4.0
2019-07-16T00:34:53.547Z
I’m sorry if my question is trivial: The OP does not give any constraint on $A$. Why is it a linear code?
Lwins
CC BY-SA 4.0
2019-07-16T06:24:24.213Z
@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.
Joshua Grochow
CC BY-SA 4.0
2019-07-15T16:44:25.750Z
2019-07-15T16:44:25.750Z
Joshua Grochow
<p>This is a follow up to <a href="https://cstheory.stackexchange.com/questions/44247/given-a-subset-of-the-hypercube-and-a-copy-translated-by-s-find-s">this resolved question</a>.
Suppose we are given a set of bitvectors <span class="math-container">$A\subseteq\mathbb{F}_2^d$</span> and an invertible affine transformed copy of it
<span class="math-container">$$B=\{Mx + s\mid x\in A\}$$</span>
for some full rank <span class="math-container">$M\in\mathbb{F}_2^{d\times d}$</span> and <span class="math-container">$s\in\mathbb{F}_2^d$</span>.</p>

<p>Given <span class="math-container">$A$</span> and <span class="math-container">$B$</span> what are the randomized and quantum complexities of finding an <span class="math-container">$M$</span> and an <span class="math-container">$s$</span> so that <span class="math-container">$MA + s = B$</span> (let us assume SETH for the purposes of this post)?</p>

<p>Does this connect to any problems studied in tcs?</p>

CC BY-SA 4.0
2019-07-14T16:20:05.603Z
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.
CC BY-SA 4.0
2019-07-14T16:24:46.863Z
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.
CC BY-SA 4.0
2019-07-17T06:19:37.247Z
This also can be expressed as finding affine equivalence between two Boolean functions (here, the characteristic functions of A and B).
Fractalic
<ds.algorithms><quantum-computing><time-complexity><boolean-functions><fourier-analysis>
Given a subset of of the hypercube and an affine transform of it, find the affine map
boinkboink
# Given a subset of of the hypercube and an affine transform of it, find the affine map

(Asked by: username_0 on 2019-07-14)

This is a follow up to [this resolved question](https://cstheory.stackexchange.com/questions/44247/given-a-subset-of-the-hypercube-and-a-copy-translated-by-s-find-s).
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?

**Tags:** ds.algorithms, quantum-computing, time-complexity, boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: 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'$.  
> **username_1**: 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.  
> **username_2**: This also can be expressed as finding affine equivalence between two Boolean functions (here, the characteristic functions of A and B).  

---

## 1 answers

### Answer by username_3 on 2019-07-15. Score: 5 | Accepted answer

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](https://groups.google.com/forum/#!msg/sci.math.research/puZxGj9HXKI/CeyH2yyyNFUJ), though it is often cited to [Petrank-Roth '97](http://dx.doi.org/10.1109/18.623157))
* 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](https://arxiv.org/abs/1907.00309)]
* The best known worst-case upper bound is $2^{O(n)}$ (due to Babai, cf. [[BCGQ11](http://dx.doi.org/10.1137/1.9781611973082.107)])
* There is an algorithm by [Sendrier 2000](http://dx.doi.org/10.1109/18.850662) that may work well in practice, depending on what kinds of codes you are looking at.

> **Comments:**
> **username_0**: Thank you! This is great  
> **username_0**: It will take me some time to digest this info  
> **username_4**: I’m sorry if my question is trivial: The OP does not give any constraint on $A$. Why is it a linear code?  
> **username_3**: @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.  

---

