Fixed Points in Spectral Complexity
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Spectral analysis has emerged as an exciting tool in complexity research. In some cases, the functions in a complexity class can be characterized by specifying a simple property of their Fourier spectra--even though their truth tables do not display such simple properties. In this paper, we demonstrate a fundamental limitation of this tool if a class of functions contains parity and is closed under some simple composition rules, then we can take the set of Fourier spectra of a subset of that class, close it under some simple projections, and obtain everything in the original class. Indeed, we can demonstrate this property for a general family of transforms, of which the parity-based Fourier transform is only one. If a class contains the basis function of such a transform, then no reduction in complexity is obtained when we shift from truth tables to spectra.
- Numerical Mathematics