On the power of circuits with gates of low L₁ norms.

DOI10.1016/S0304-3975(96)00290-3MaRDI QIDQ1389652zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• Norms, XOR lemmas, and lower bounds for polynomials and protocols

Cites work

• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• scientific article; zbMATH DE number 177818 (Why is no real title available?)
• scientific article; zbMATH DE number 1256663 (Why is no real title available?)
• scientific article; zbMATH DE number 1332656 (Why is no real title available?)
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• scientific article; zbMATH DE number 3327849 (Why is no real title available?)
• A weight-size trade-off for circuits with MOD \(m\) gates
• Constant depth circuits, Fourier transform, and learnability
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Majority gates vs. general weighted threshold gates
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the degree of Boolean functions as real polynomials
• On the power of small-depth threshold circuits
• Representing Boolean functions as polynomials modulo composite numbers
• The expressive power of voting polynomials
• Threshold circuits of bounded depth
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(5)

• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Approximate F_2-Sketching of Valuation Functions
• Boolean functions with small spectral norm, revisited
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Norms, XOR lemmas, and lower bounds for polynomials and protocols

This page was built for publication: On the power of circuits with gates of low \(L_{1}\) norms.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1389652)