Communication Complexity and Quasi Randomness
From MaRDI portal
Publication:5285941
DOI10.1137/0406009zbMath0771.05073OpenAlexW2044575164MaRDI QIDQ5285941
Fan R. K. Chung, Prasad Tetali
Publication date: 29 June 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406009
hypergraphdiscrepancylower boundsBoolean functionmultiparty communication complexitymultiparty protocolsquasi randomness
Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorial probability (60C05) Turing machines and related notions (03D10)
Related Items
Hellinger volume and number-on-the-forehead communication complexity, Hadamard tensors and lower bounds on multiparty communication complexity, Unnamed Item, On a theorem of Razborov, Interleaved Group Products, The NOF multiparty communication complexity of composed functions, Quasi-random subsets of \(\mathbb{Z}_ n\), The communication complexity of addition, One-way multiparty communication lower bound for pointer jumping with applications, Quasi-random hypergraphs revisited, Pseudorandom Functions: Three Decades Later, Some applications of hypercontractive inequalities in quantum information theory, Hypergraphs, quasi-randomness, and conditions for regularity
