<p>Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.</p>

CC BY-SA 3.0
2014-02-21T14:32:41.670Z
Do you think this problem is harder than *matrix product verification* problem (there is a link at the end of question)?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2014-02-19T23:01:04.063Z
2014-02-19T23:01:04.063Z
David Harris
<p>While this doesn't answer your exact question, CFG parsing is a decision problem that was reduced from matrix multiplication (so it is as hard as matrix multiplication in a sense).</p>

<p>Specifically, in <a href="http://arxiv.org/pdf/cs/0112018.pdf" rel="nofollow">[1]</a> it was shown that CFG parsing is as hard as boolean matrix multiplication.  In particular, if CFG parsing (a decision problem) can be solved in $O(gn^{3-\epsilon})$ time, boolean matrix multiplication can be solved in $O(n^{3-\epsilon/3})$ time.  An interesting aspect is that matrix multiplication can also be used for fast CFG algorithms, so the problems are computationally equivalent in a sense.</p>

<p>The reduction has some unusual aspects because boolean matrix multiplication requires $n^2$ output bits, whereas CFG parsing only requires one.  To deal with this, the paper assumes that the CFG parser solves certain subproblems when parsing the string (and argues that this is a reasonable assumption to make).  The reduction makes $n^2$ queries to these subproblems to obtain the product matrix.</p>

<p>Thus CFG parsing is a decision problem that is computationally as hard (in a sense) as matrix multiplication.  However, this is not specifically a decision version of matrix multiplication, and furthermore, the reduction relies on the idea that CFG parsing is actually made up of $n^2$ decision subproblems.</p>

<ol>
<li>Lee, Lillian. "Learning of context-free languages: A survey of the literature." Techn. Rep. TR-12-96, Harvard University (1996).</li>
</ol>

CC BY-SA 3.0
2014-02-21T19:07:16.273Z
2014-02-21T19:07:16.273Z
SamM
<p>Is there any known decision version of matrix multiplication problem such that the time complexity of <em>the best known algorithm</em> for this decision problem is $O(n^k)$ for $n \times n$-dimensional matrices, where $k$ is bigger than 2 and preferable very close to $ \omega $ or the best known candidate of $\omega$ ($\omega$ is the optimal matrix-product constant)? </p>

<p>P.S. I am aware of <em>matrix product verification</em> problem (e.g. <a href="https://cstheory.stackexchange.com/q/5936/7358">this post</a>). </p>

CC BY-SA 3.0
2014-02-19T22:58:27.370Z
Crypto really isn't my field, but what about computing the $k$th bit of some cryptographic hash function of the matrix product (or a similar trick)?
Yonatan N
<reference-request><matrix-product>
Decision version of matrix multiplication problem
Abuzer Yakaryilmaz
# Decision version of matrix multiplication problem

(Asked by: username_0 on 2014-02-19)

Is there any known decision version of matrix multiplication problem such that the time complexity of *the best known algorithm* for this decision problem is $O(n^k)$ for $n \times n$-dimensional matrices, where $k$ is bigger than 2 and preferable very close to $ \omega $ or the best known candidate of $\omega$ ($\omega$ is the optimal matrix-product constant)?

P.S. I am aware of *matrix product verification* problem (e.g. [this post](https://cstheory.stackexchange.com/q/5936/7358)).

**Tags:** reference-request, matrix-product

> **Comments:**
> **username_1**: Crypto really isn't my field, but what about computing the $k$th bit of some cryptographic hash function of the matrix product (or a similar trick)?  

---

## 2 answers

### Answer by username_2 on 2014-02-19. Score: 2

Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.

> **Comments:**
> **username_0**: Do you think this problem is harder than *matrix product verification* problem (there is a link at the end of question)?  

---

### Answer by username_3 on 2014-02-21. Score: 1

While this doesn't answer your exact question, CFG parsing is a decision problem that was reduced from matrix multiplication (so it is as hard as matrix multiplication in a sense).

Specifically, in [[1]](http://arxiv.org/pdf/cs/0112018.pdf) it was shown that CFG parsing is as hard as boolean matrix multiplication. In particular, if CFG parsing (a decision problem) can be solved in $O(gn^{3-\epsilon})$ time, boolean matrix multiplication can be solved in $O(n^{3-\epsilon/3})$ time. An interesting aspect is that matrix multiplication can also be used for fast CFG algorithms, so the problems are computationally equivalent in a sense.

The reduction has some unusual aspects because boolean matrix multiplication requires $n^2$ output bits, whereas CFG parsing only requires one. To deal with this, the paper assumes that the CFG parser solves certain subproblems when parsing the string (and argues that this is a reasonable assumption to make). The reduction makes $n^2$ queries to these subproblems to obtain the product matrix.

Thus CFG parsing is a decision problem that is computationally as hard (in a sense) as matrix multiplication. However, this is not specifically a decision version of matrix multiplication, and furthermore, the reduction relies on the idea that CFG parsing is actually made up of $n^2$ decision subproblems.

1. Lee, Lillian. "Learning of context-free languages: A survey of the literature." Techn. Rep. TR-12-96, Harvard University (1996).


---

