<p>Essentially, your are asking why people believe that DFT or DHT do not have linear size arithmetic circuits. First, researcher tried to find such circuits for decades but did not succeed. Second, there are superlinear lower bounds (Morgenstern's theorem, see the book by Bürgisser, Clausen, Shokrollahi) in restricted models. From Morgenstern's theorem, in follows that in linear arithmetic circuits of linear size over the complex numbers  for the DFT, the absolute values of the constants used in the circuit go to infinity as $n$ goes to infinity. </p>

CC BY-SA 3.0
2012-06-18T09:30:51.040Z
Hi Markus: Could you explain what do you mean by "the absolute values of the constants go to infinity" and how close the restricted models are to reality?
Turbo
CC BY-SA 3.0
2012-06-18T09:51:35.400Z
@Arul: Maybe it is easier to phrase it the other way: If the absolute values of the scalars occuring in the circuits are bounded by some constant, then we have an $\Omega(n \log n)$ lower bound.
Markus Bläser
CC BY-SA 3.0
2012-06-18T16:49:49.727Z
Hi Markus: I am unfamiliar with Morgenstern's theorem. It seems from what you are saying several researcher's tried and failed. The constants are unbounded. It seems to me that this is an evidence of failure in assumption that lower bound is superlinear. It does not explain why a superlinear lower bound is conjectured except people have failed.
Turbo
CC BY-SA 3.0
2012-06-18T16:51:31.800Z
Can you provide original reference and standard citations?
Turbo
CC BY-SA 3.0
2012-06-18T18:51:55.567Z
Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory, Springer, Theorem 13.14. Originally proved in the thesis of J. Morgenstern. Note that although in the general model, arbitrarily large constants can be used, it is not clear how to use them when computing the DFT, since all coefficients in the DFT matrix are bounded.
Markus Bläser
CC BY-SA 3.0
2012-06-18T19:18:14.103Z
Hi Markus: It is still unclear why they would be conjectured to be superlinear complexity given that Morgenstern's results lead to guess otherwise (from what you are stating it seems if the constants are bounded this would be superlinear but it seems it is not obvious how to use them in a bounded way as you are stating and it also seems to be unbounded if used the way Morgenstern used it). The only evidence seems to me from an indirect source, namely, this would lead integer multiplication and addition of same potential complexity. However I need to look at the references you are stating.
Turbo
CC BY-SA 3.0
2012-08-05T17:07:31.450Z
Arul your sentence in the parenthesis is impossible to parse. We do not know of a single algebraic problem given by a matrix with bounded entries for which large constants in the computation leads to faster algorithms. Moreover, a linear time algorithm for DFT would prove that the DFT matrix has low rigidity, which is hard to imagine.
Sasho Nikolov
CC BY-SA 3.0
2012-06-18T09:19:07.683Z
2012-06-18T18:53:48.987Z
2012-06-18T18:53:48.987Z
Markus Bläser
<p>Why are standard unitary transforms such as the Fourier and the Hadamard transforms believed to have a multiplicative complexity (number of multiplications) of $O(n^{1+\delta_{m}})$ and an additive complexity of $O(n^{1+\delta_{a}})$ (number of additions) where both $\delta_{m}$ and $\delta_{a}$ cannot be $0$ simultaneously?</p>

<p>(Please refer: Section 2.2 Page 15 of "Complexity Lower Bounds Using Linear Algebra", by Satyanarayana V. Lokam, for candidate matrices conjectured to have an arithmetic complexity (multiplicative + additive complexity)  of $\Omega(n^{1+\delta})$).</p>

CC BY-SA 3.0
2012-06-15T20:45:31.593Z
Can you provide a source for the above claims? Specifically, I don't know what you mean by 'Hadamard' transform in this case, as the operation I most commonly know by Hadamard has by definition a complexity of precisely 1 in the usual elementary gate sets discussed in the literature.
Niel de Beaudrap
CC BY-SA 3.0
2012-06-15T20:56:14.180Z
http://en.wikipedia.org/wiki/Hadamard_transform
Turbo
CC BY-SA 3.0
2012-06-15T21:09:03.990Z
What are "multiplicative complexity" and "additive complexity"?
Robin Kothari
CC BY-SA 3.0
2012-06-15T21:35:35.797Z
You really need a reference for the claim, as Niel indicates
Suresh Venkat
CC BY-SA 3.0
2012-06-16T04:30:39.150Z
@SureshVenkat A reference is added.
Turbo
CC BY-SA 3.0
2012-06-16T15:32:58.880Z
It would be quite helpful if you could answer Robin's question.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-16T17:26:17.660Z
@JoeFitzsimons I think I answered it. I edited and introduced the words number of additions/multiplications
Turbo
CC BY-SA 3.0
2012-06-16T20:18:17.180Z
@Arul: The reference you provide isn't complete, and even if it was, it's asking a lot to get people to go off to read a paper to understand your question.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-16T21:51:28.853Z
Actually, all of the people asking questions are quantum people, but it just occurred to me that this might be a question entirely about classical computation. I think we've all been thinking of this in terms of quantum circuit complexity (see Niel's comment for instance). Is this the case?
Joe Fitzsimons
CC BY-SA 3.0
2012-06-16T23:02:31.880Z
@JoeFitzsimons: I've come to the conclusion myself that it isn't about quantum circuit complexity; my own comment was a knee-jerk reaction (as you've surmised), and I've only refrained from deleting it because of other people's references to it. It makes absolutely no sense to refer to the "additive" or "multiplicative" complexity of the Walsh-Hadamard transform as a quantum operation --- on qubits, anyway --- for anyone capable of finding a reference to it.
Niel de Beaudrap
CC BY-SA 3.0
2012-06-17T05:09:18.167Z
Haha this is just plain classical complexity. I am unfortunately illiterate in QC and I apologize for the lack of clarity!
Turbo
CC BY-SA 3.0
2012-06-17T14:12:38.393Z
@Arul: Sorry! I was trying to figure out what arithmetic complexity meant in quantum circuits. You don't say anything to indicate a quantum interpretation, but these operations are so synonymous with quantum computing that I just assumed a quantum context.
Joe Fitzsimons
<cc.complexity-theory><algebraic-complexity>
Classical Matrix-Vector multiplication Complexity of standard matrices
Turbo
# Classical Matrix-Vector multiplication Complexity of standard matrices

(Asked by: username_0 on 2012-06-15)

Why are standard unitary transforms such as the Fourier and the Hadamard transforms believed to have a multiplicative complexity (number of multiplications) of $O(n^{1+\delta\_{m}})$ and an additive complexity of $O(n^{1+\delta\_{a}})$ (number of additions) where both $\delta\_{m}$ and $\delta\_{a}$ cannot be $0$ simultaneously?

(Please refer: Section 2.2 Page 15 of "Complexity Lower Bounds Using Linear Algebra", by Satyanarayana V. Lokam, for candidate matrices conjectured to have an arithmetic complexity (multiplicative + additive complexity) of $\Omega(n^{1+\delta})$).

**Tags:** cc.complexity-theory, algebraic-complexity
> **Comments:**
> **username_1**: Can you provide a source for the above claims? Specifically, I don't know what you mean by 'Hadamard' transform in this case, as the operation I most commonly know by Hadamard has by definition a complexity of precisely 1 in the usual elementary gate sets discussed in the literature.  
> **username_0**: http://en.wikipedia.org/wiki/Hadamard_transform  
> **username_2**: What are "multiplicative complexity" and "additive complexity"?  
> **username_3**: You really need a reference for the claim, as Niel indicates  
> **username_0**: @SureshVenkat A reference is added.  
> **username_4**: It would be quite helpful if you could answer Robin's question.  
> **username_0**: @JoeFitzsimons I think I answered it. I edited and introduced the words number of additions/multiplications  
> **username_4**: @Arul: The reference you provide isn't complete, and even if it was, it's asking a lot to get people to go off to read a paper to understand your question.  
> **username_4**: Actually, all of the people asking questions are quantum people, but it just occurred to me that this might be a question entirely about classical computation. I think we've all been thinking of this in terms of quantum circuit complexity (see Niel's comment for instance). Is this the case?  
> **username_1**: @JoeFitzsimons: I've come to the conclusion myself that it isn't about quantum circuit complexity; my own comment was a knee-jerk reaction (as you've surmised), and I've only refrained from deleting it because of other people's references to it. It makes absolutely no sense to refer to the "additive" or "multiplicative" complexity of the Walsh-Hadamard transform as a quantum operation --- on qubits, anyway --- for anyone capable of finding a reference to it.  
> **username_0**: Haha this is just plain classical complexity. I am unfortunately illiterate in QC and I apologize for the lack of clarity!  
> **username_4**: @Arul: Sorry! I was trying to figure out what arithmetic complexity meant in quantum circuits. You don't say anything to indicate a quantum interpretation, but these operations are so synonymous with quantum computing that I just assumed a quantum context.  

---

## 1 answers

### Answer by username_5 on 2012-06-18. Score: 3 | Accepted answer

Essentially, your are asking why people believe that DFT or DHT do not have linear size arithmetic circuits. First, researcher tried to find such circuits for decades but did not succeed. Second, there are superlinear lower bounds (Morgenstern's theorem, see the book by Bürgisser, Clausen, Shokrollahi) in restricted models. From Morgenstern's theorem, in follows that in linear arithmetic circuits of linear size over the complex numbers for the DFT, the absolute values of the constants used in the circuit go to infinity as $n$ goes to infinity.

> **Comments:**
> **username_0**: Hi Markus: Could you explain what do you mean by "the absolute values of the constants go to infinity" and how close the restricted models are to reality?  
> **username_5**: @Arul: Maybe it is easier to phrase it the other way: If the absolute values of the scalars occuring in the circuits are bounded by some constant, then we have an $\Omega(n \log n)$ lower bound.  
> **username_0**: Hi Markus: I am unfamiliar with Morgenstern's theorem. It seems from what you are saying several researcher's tried and failed. The constants are unbounded. It seems to me that this is an evidence of failure in assumption that lower bound is superlinear. It does not explain why a superlinear lower bound is conjectured except people have failed.  
> **username_0**: Can you provide original reference and standard citations?  
> **username_5**: Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory, Springer, Theorem 13.14. Originally proved in the thesis of J. Morgenstern. Note that although in the general model, arbitrarily large constants can be used, it is not clear how to use them when computing the DFT, since all coefficients in the DFT matrix are bounded.  
> **username_0**: Hi Markus: It is still unclear why they would be conjectured to be superlinear complexity given that Morgenstern's results lead to guess otherwise (from what you are stating it seems if the constants are bounded this would be superlinear but it seems it is not obvious how to use them in a bounded way as you are stating and it also seems to be unbounded if used the way Morgenstern used it). The only evidence seems to me from an indirect source, namely, this would lead integer multiplication and addition of same potential complexity. However I need to look at the references you are stating.  
> **username_6**: Arul your sentence in the parenthesis is impossible to parse. We do not know of a single algebraic problem given by a matrix with bounded entries for which large constants in the computation leads to faster algorithms. Moreover, a linear time algorithm for DFT would prove that the DFT matrix has low rigidity, which is hard to imagine.  

---

