1
$\begingroup$

Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.

Let $x=[x_1,x_2,\ldots,x_n]'$ be given vector and $F$ be Fourier transform matrix.

It is not known if $F(x)$ needs $n\log n$ operations in the unbounded coefficient model when $x_i$'s are treated generically as variables.

Supposing each $x_i$ is an integer bounded by $2^b$, can one show computing $F(x)$ still needs $n\log n$ arithmetic operations in the unbounded coefficient model?

Added: The reason I posted was a few fold. Some questions in the bounded integer $x_i$ model are:

1) We cannot use bit level manipulation on variables $x_i$. However we can do bit level operations on integers $x_i$. Are bit level operations considered valid arithmetic operations when counting the $\Omega(n\log n)$ arithmetic operation?

2) Does one multiplication operation on a word that scales as $O(n)$ bits still count as $1$ arithmetic operation?

3) Is division a valid arithmetic operation?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I don't see the point of 1: allowing bit level manipulations increases the power of the model, so it can only make lower bounds more difficult to prove. AFAIK, in the straight line program model bit level manipulations are not allowed. Moreover, I think the model Morgenstern uses is in fact a linear circuit, i.e. the value at each gate is a linear function of the input. $\endgroup$
    – Sasho Nikolov
    Jun 22, 2013 at 4:52

1 Answer 1

Reset to default
4
$\begingroup$

Of course if you show a lower bound of $\Omega(n \log n)$ for your question, it would imply the same lower bound for the unrestricted model, which is not known.

On the other hand, you are asking whether it is possible to compute the Fourier transform where each $x_i$ is known within $b$ bits of precision using $\ll n \log n$ arithmetic operations. If true, by the fact that the Fourier transform is a unitary operation (and thus, perfectly conditioned), we would be able to compute Fourier transform of any vector within $b$ bits of precision much faster than FFT, which is certainly not known either.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thankyou. The reason I posted was a few fold: 1) We cannot use bit level manipulation on variables $xi$. However we can do bit level operations on integers $xi$. Are bit level operations a valid arithmetic operation when counting the $\Omega(nlogn)$ arithmetic operation? 2) Does one multiplication operation on a word that scales as $O(n)$ bits still count as $1$ arithmetic operation? 3) Is division a valid operation? $\endgroup$
    – Turbo
    Jun 21, 2013 at 18:57
  • 2
    $\begingroup$ If you normalize everything by a factor of $2^b$, your model becomes equivalent with one where every $x_i$ is in $[0,1]$ and truncated to $b$ bits of precision. Division by a scalar is of course allowed in the straight line program model. Addition and scalar multiplication are considered to have cost $1$. $\endgroup$
    – Mahdi Cheraghchi
    Jun 21, 2013 at 20:36
  • $\begingroup$ So multiplication operation on a word that scales as O(n) bits still count as 1 arithmetic operation. Thankyou. One last question can we include floor and ceil to be one arithmetic operation? $\endgroup$
    – Turbo
    Jun 22, 2013 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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