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 -