GEOMETRICAL REALIZATION OF SET SYSTEMS AND PROBABILISTIC COMMUNICATION COMPLEXITY.

N. Alon, P. Frankl, V. Roedl

Research output: Chapter in Book/Report/Conference proceedingConference contribution

71 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages277-280
Number of pages4
ISBN (Print)0818606444, 9780818606441
DOIs
StatePublished - 1985
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'GEOMETRICAL REALIZATION OF SET SYSTEMS AND PROBABILISTIC COMMUNICATION COMPLEXITY.'. Together they form a unique fingerprint.

Cite this