Evaluating spectral norms for constant depth circuits with symmetric gates

DOI10.1007/BF01268144zbMath0838.68040MaRDI QIDQ1904669

Sitharam, Meera

Publication date: 27 May 1996

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

circuit complexityFourier spectrum

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of computing (68Q99)

Related Items (1)

A NOTE ON THE POLYNOMIAL REPRESENTATION OF BOOLEAN FUNCTIONS OVER GF(2)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Approximate inclusion-exclusion
• Majority gates vs. general weighted threshold gates
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Representing Boolean functions as polynomials modulo composite numbers
• Parity, circuits, and the polynomial-time hierarchy
• Harmonic Analysis of Polynomial Threshold Functions
• On the Power of Threshold Circuits with Small Weights
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Learning Decision Trees Using the Fourier Spectrum

This page was built for publication: Evaluating spectral norms for constant depth circuits with symmetric gates