TY - GEN
T1 - GEOMETRICAL REALIZATION OF SET SYSTEMS AND PROBABILISTIC COMMUNICATION COMPLEXITY.
AU - Alon, N.
AU - Frankl, P.
AU - Roedl, V.
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 1985
Y1 - 1985
N2 - Let d equals d(n) be the minimum d such that for every sequence of n subsets F//1, F//2,. . . , F//N of left brace 1, 2,. . . , n right brace there exist n points P//1 P//2,. . . , P//N and n hyperplanes H//1 H//2,. . . , H//N in R**D such that P//J lies in the positive side of H//I if and only if j epsilon F//I. Then n/32 less than equivalent to d(n) less than equivalent to (1/2 plus o(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 some open problems.
AB - Let d equals d(n) be the minimum d such that for every sequence of n subsets F//1, F//2,. . . , F//N of left brace 1, 2,. . . , n right brace there exist n points P//1 P//2,. . . , P//N and n hyperplanes H//1 H//2,. . . , H//N in R**D such that P//J lies in the positive side of H//I if and only if j epsilon F//I. Then n/32 less than equivalent to d(n) less than equivalent to (1/2 plus o(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 some open problems.
UR - http://www.scopus.com/inward/record.url?scp=0022188126&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022188126&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1985.30
DO - 10.1109/sfcs.1985.30
M3 - Conference contribution
AN - SCOPUS:0022188126
SN - 0818606444
SN - 9780818606441
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 277
EP - 280
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -