Geometric arguments yield better bounds for threshold circuits and distributed computing

DOI10.1016/0304-3975(95)00005-4zbMath0887.68034OpenAlexW2071020383MaRDI QIDQ1365681

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

Related Items (8)

A linear lower bound on the unbounded error probabilistic communication complexity. ⋮ On relations between counting communication complexity classes ⋮ Around the log-rank conjecture ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Extended formulations, nonnegative factorizations, and randomized communication protocols ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Quantum State Complexity of Formal Languages ⋮ Upper bounds on communication in terms of approximate rank

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Harmonic Analysis of Polynomial Threshold Functions

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