Geometrical realization of set systems and probabilistic communication complexity
- 1 October 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 277-280
- https://doi.org/10.1109/sfcs.1985.30
Abstract
Let d = d(n) be the minimum d such that for every sequence of n subsets F1, F2, . . . , Fn of {1, 2, . . . , n} there exist n points P1, P2, . . . , Pn and n hyperplanes H1, H2 .... , Hn in Rd such that Pj lies in the positive side of Hi iff j ∈ Fi. Then n/32 ≤ d(n) ≤ (1/2 + 0(1)) · n. This implies that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon. The proof of (1) combines some known geometric facts with certain probabilistic arguments and a theorem of Milnor from real algebraic geometry.Keywords
This publication has 7 references indexed in Scilit:
- Probabilistic Communication ComplexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sourcesPublished by Association for Computing Machinery (ACM) ,1985
- Unbiased bits from sources of weak randomness and probabilistic communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Multidimensional SortingSIAM Journal on Computing, 1983
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979
- The number of partitions of a set of N points in k dimensions induced by hyperplanesProceedings of the Edinburgh Mathematical Society, 1967
- On the Betti Numbers of Real VarietiesProceedings of the American Mathematical Society, 1964