<p>NP-hardness is proved by Roth and Viswanathan in the paper <a href="https://doi.org/10.1109/TIT.2007.915716" rel="noreferrer">On the hardness of decoding the gale-berlekamp code</a></p>

CC BY-SA 4.0
2021-06-28T14:13:09.757Z
Thank you very much! I also found a proof in https://doi.org/10.1287/moor.2017.0895.
W. Mapa
CC BY-SA 4.0
2021-06-29T21:46:34.557Z
Yes - They appear to have rediscovered the proof of Roth and Viswanathan.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-06-27T14:14:18.243Z
2021-06-27T14:14:18.243Z
Kristoffer Arnsfelt Hansen
<p>My question concerns the NP-hardness of the following discrete optimization problem:</p>
<p>Given a matrix <span class="math-container">$A \in \{ \pm 1 \}^{m\times n}$</span>,</p>
<p><span class="math-container">$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm 1 \}^n}{\text{maximize}} &amp; x^T A \, y\end{array}$$</span></p>
<p>Is this problem known to be NP-hard?</p>

CC BY-SA 4.0
2021-06-23T19:24:11.387Z
If $A$ can also have zero entries, then it is NP-hard. I doubt this is really necessary, but I don't have an immediate argument for this.
Jason Gaitonde
<cc.complexity-theory><np-hardness><co.combinatorics><optimization>
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
W. Mapa
# Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

(Asked by: username_0 on 2021-06-23)

My question concerns the NP-hardness of the following discrete optimization problem:

Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,

$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm 1 \}^n}{\text{maximize}} & x^T A \, y\end{array}$$

Is this problem known to be NP-hard?

**Tags:** cc.complexity-theory, np-hardness, co.combinatorics, optimization

> **Comments:**
> **username_1**: If $A$ can also have zero entries, then it is NP-hard. I doubt this is really necessary, but I don't have an immediate argument for this.  

---

## 1 answers

### Answer by username_2 on 2021-06-27. Score: 6 | Accepted answer

NP-hardness is proved by Roth and Viswanathan in the paper [On the hardness of decoding the gale-berlekamp code](https://doi.org/10.1109/TIT.2007.915716)

> **Comments:**
> **username_0**: Thank you very much! I also found a proof in https://doi.org/10.1287/moor.2017.0895.  
> **username_2**: Yes - They appear to have rediscovered the proof of Roth and Viswanathan.  

---

