# divide and conquer

Published articles for divide and conquer.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details

DevFeed: [A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details](<https://devfeed.tech/articles/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details-40391.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/>)

Published: 2015-11-12T09:00:00Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Computer science](<https://devfeed.tech/topics/computer-science.md>), [math](<https://devfeed.tech/topics/math.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [automorphism-groups](<https://devfeed.tech/tags/automorphism-groups.md>), [babai](<https://devfeed.tech/tags/babai.md>), [breakthrough](<https://devfeed.tech/tags/breakthrough.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [divide-and-conquer](<https://devfeed.tech/tags/divide-and-conquer.md>), [graph-isomorphism](<https://devfeed.tech/tags/graph-isomorphism.md>), [group-theory](<https://devfeed.tech/tags/group-theory.md>), [johnson-graph](<https://devfeed.tech/tags/johnson-graph.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [permutation-groups](<https://devfeed.tech/tags/permutation-groups.md>), [quasipolynomial](<https://devfeed.tech/tags/quasipolynomial.md>), [research](<https://devfeed.tech/tags/research.md>)

### AI overview

This research-level blog post explains Laszlo Babai's claimed quasipolynomial-time algorithm for the Graph Isomorphism problem. Later updates report that an error was found, changing the result to sub-exponential time, followed by a claimed workaround restoring the quasipolynomial-time claim.

### Source excerpt

Update 2017-01-09: Laci claims to have found a workaround to the previously posted error, and the claim is again quasipolynoimal time! Updated arXiv paper to follow. Update 2017-01-04: Laci has posted an update on his paper. The short version is that one small step of his analysis was not quite correct, and the result is that his algorithm is sub-exponential, but not quasipolynomial time. The fact that this took over a year to sort out is a testament to the difficulty of the mathematics and the skill of the mathematicians involved.

## The Fast Fourier Transform

DevFeed: [The Fast Fourier Transform](<https://devfeed.tech/articles/the-fast-fourier-transform-40280.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/07/18/the-fast-fourier-transform/>)

Published: 2012-07-18T08:00:54Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [processing](<https://devfeed.tech/topics/processing.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [audio](<https://devfeed.tech/tags/audio.md>), [divide-and-conquer](<https://devfeed.tech/tags/divide-and-conquer.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [graphics](<https://devfeed.tech/tags/graphics.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [processing](<https://devfeed.tech/tags/processing.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [signal-processing](<https://devfeed.tech/tags/signal-processing.md>), [sound](<https://devfeed.tech/tags/sound.md>)

### AI overview

A tutorial on the Fast Fourier Transform explains its historical development, the improvement from O(n^2) to O(n log n) computation for the discrete Fourier transform, and a derivation and implementation approach. It also explores audio denoising by filtering a noisy signal's frequency spectrum.

### Source excerpt

It's often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey's paper, "An Algorithm for the Machine Calculation of Complex Fourier Series." They published a landmark algorithm which has since been called the Fast Fourier Transform algorithm, and has spawned countless variations. Specifically, it improved the best known computational bound on the discrete Fourier transform from $ O(n^2)$ to $ O(n \log n)$, which is the difference between uselessness and panacea.