Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky

DOI10.1007/BF01294254zbMath0890.68062OpenAlexW2067616141MaRDI QIDQ1377573

Jehoshua Bruck

Publication date: 11 February 1998

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

Full work available at URL: https://doi.org/10.1007/bf01294254

zbMATH Keywords

Boolean functionscircuit complexity

Mathematics Subject Classification ID

Boolean functions (06E30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99)

Cites Work

• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Representations of sets of Boolean functions by commutative rings
• Constant depth circuits, Fourier transform, and learnability
• Harmonic Analysis of Polynomial Threshold Functions
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Learning Decision Trees Using the Fourier Spectrum
• Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
• Unnamed Item

This page was built for publication: Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky