Fixed Points in Spectral Complexity

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1992
Accession Number
ADA256729

Entities

People

  • Carl Sturtivant
  • Sean W. Smith

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Air Force
  • Algebra
  • Automata
  • Computational Complexity
  • Computer Science
  • Eigenvalues
  • Eigenvectors
  • Fourier Analysis
  • Fourier Transformation
  • Linear Algebra
  • Personality
  • Point Theorem
  • Polynomials
  • Spectra
  • Standards
  • Vector Spaces

Readers

  • Computer Programming and Software Development.
  • Graph Algorithms and Convex Optimization.
  • Statistical inference.