Papers
www.cs.dartmouth.edu/~sws/abstracts/ss92.shtml
Last modified: 08/27/03 11:56:54 AM

S.W. Smith, C. Sturtivant.
Fixed Points in Spectral Complexity.
Technical Report CMU-CS-92-190, Department of Computer Science, Carnegie Mellon University.
October 1992.

Abstract

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.

Download

PDF.

Back to home page Maintained by Sean Smith, sws@cs.dartmouth.edu