Geometric arguments yield better bounds for threshold circuits and distributed computing

DOI10.1016/0304-3975(95)00005-4MaRDI QIDQ1365681zbMATH OpenOpenAlexFDO

Authors Matthias Krause

Publication date 9 September 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(95)00005-4

zbMATH Keywords

Boolean functionsthreshold circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in artificial intelligence (68T27)

Recommendations

• scientific article; zbMATH DE number 2081103
• On the power of circuits with gates of low \(L_{1}\) norms.
• Lower bounds on threshold and related circuits via communication complexity
• scientific article; zbMATH DE number 1256716

Cites work

• scientific article; zbMATH DE number 4213443 (Why is no real title available?)
• scientific article; zbMATH DE number 177818 (Why is no real title available?)
• Harmonic Analysis of Polynomial Threshold Functions
• Majority gates vs. general weighted threshold gates
• On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
• Realizing Boolean functions on disjoint sets of variables

Cited in

(13)

• Quantum state complexity of formal languages
• Upper bounds on communication in terms of approximate rank
• Some New Classes of Geometric Threshold Schemes
• Fooling pairs in randomized communication complexity
• Threshold circuit lower bounds on cryptographic functions
• Around the log-rank conjecture
• scientific article; zbMATH DE number 2081103 (Why is no real title available?)
• On relations between counting communication complexity classes
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Lower bounds on threshold and related circuits via communication complexity
• Upper bounds on communication in terms of approximate rank
• Approximate nonnegative rank is equivalent to the smooth rectangle bound
• Norms, XOR lemmas, and lower bounds for polynomials and protocols

This page was built for publication: Geometric arguments yield better bounds for threshold circuits and distributed computing

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