On the power of circuits with gates of low \(L_{1}\) norms.

DOI10.1016/S0304-3975(96)00290-3zbMath1053.68575OpenAlexW2057810289MaRDI QIDQ1389652

Vince Grolmusz

Publication date: 30 June 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00290-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximate F_2-Sketching of Valuation Functions ⋮ On the structure of Boolean functions with small spectral norm ⋮ Unnamed Item ⋮ Boolean functions with small spectral norm, revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of small-depth threshold circuits
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Majority gates vs. general weighted threshold gates
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• The expressive power of voting polynomials
• On the degree of Boolean functions as real polynomials
• Representing Boolean functions as polynomials modulo composite numbers
• Threshold circuits of bounded depth
• A weight-size trade-off for circuits with MOD m gates
• Constant depth circuits, Fourier transform, and learnability
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Monotone circuits for matching require linear depth