Geometric arguments yield better bounds for threshold circuits and distributed computing
From MaRDI portal
Publication:1365681
DOI10.1016/0304-3975(95)00005-4zbMath0887.68034MaRDI QIDQ1365681
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
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, Around the log-rank conjecture, 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, Upper bounds on communication in terms of approximate rank, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Fooling Pairs in Randomized Communication Complexity
Cites Work