Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
- 26 November 2001
- book chapter
- Published by Springer Nature
- p. 171-182
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in2002
- Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces2001
- Limitations of Learning via Embeddings in Euclidean Half-Spaces2001
- On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions1999
- Geometric arguments yield better bounds for threshold circuits and distributed computingTheoretical Computer Science, 1996
- Different Modes of CommunicationSIAM Journal on Computing, 1993
- Threshold circuits of bounded depthJournal of Computer and System Sciences, 1993
- Meanders and their applications in lower bounds argumentsJournal of Computer and System Sciences, 1988
- Probabilistic communication complexityJournal of Computer and System Sciences, 1986
- Geometrical realization of set systems and probabilistic communication complexity1985