Geometric arguments yield better bounds for threshold circuits and distributed computing

DOI10.1016/0304-3975(95)00005-4zbMath0887.68034MaRDI 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 functions; threshold circuit

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T27: Logic in artificial intelligence

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item