3
$\begingroup$

The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths).

However, while the fast Fourier transform algorithm implies several other near-linear-time algebraic algorithms including polynomial multiplication, multi-point evaluation, interpolation, etc., I do not know its application to any graph problem yet.

What are applications of the fast Fourier transform to graph problems?

Actually, applications other fast algebraic algorithms (except fast matrix multiplication) are also welcomed.

$\endgroup$
  • 3
    $\begingroup$ My rough take is that FFT is essentially about 1D structures, whereas matrix multiplication is (in some fairly precise sense) its "2D" analogue. Graphs are definitely not 1D, and one can argue they are 2D because they about pairwise relationships (viz. the adjacency matrix). This analogy isn't perfect, nor precise, but perhaps explains at a high level why there are more applications of matrix multiplication than FFT to graphs. I'll be interested to see if there are examples! $\endgroup$ – Joshua Grochow Feb 20 '18 at 4:09
  • 2
    $\begingroup$ FFT is used for exponential-time algorithms for NP-hard problems on graphs. See, for example, 1. Theorem 7.8 in ii.uib.no/~fomin/BookEA/BookEA.pdf 2. citeseerx.ist.psu.edu/viewdoc/… 3. people.csail.mit.edu/rrw/presentations/subset-conv.pdf $\endgroup$ – Alex Golovnev Feb 20 '18 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.