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

DOI10.1016/S0304-3975(96)00290-3zbMATH Open1053.68575OpenAlexW2057810289MaRDI QIDQ1389652FDOQ1389652

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Approximate F_2-Sketching of Valuation Functions
• Boolean functions with small spectral norm, revisited
• On the structure of Boolean functions with small spectral norm

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)