Communication Complexity and Quasi Randomness

DOI10.1137/0406009MaRDI QIDQ5285941zbMATHOpenAlexFDO

Authors Fan 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

zbMATH Keywords

discrepancylower boundsBoolean functionhypergraphmultiparty communication complexitymultiparty protocolsquasi randomness

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Hypergraphs (05C65) Turing machines and related notions (03D10)

Recommendations

• Quasi‐random classes of hypergraphs
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Multiparty communication complexity and very hard functions
• Automata, Languages and Programming

Cited in

(21)

• The NOF multiparty communication complexity of composed functions
• Communication and Randomness Lower Bounds for Secure Computation
• Some applications of hypercontractive inequalities in quantum information theory
• The Communication Complexity of Non-signaling Distributions
• Simultaneous multiparty communication protocols for composed functions
• Hadamard tensors and lower bounds on multiparty communication complexity
• Quasi-random Boolean functions
• Communication complexity of key agreement on small ranges
• Average and randomized communication complexity
• Pseudorandom functions: three decades later
• The communication complexity of addition
• Quasi-random subsets of \(\mathbb{Z}_ n\)
• Interleaved Group Products
• One-way multiparty communication lower bound for pointer jumping with applications
• Quasi-random hypergraphs revisited
• On a theorem of Razborov
• Non-deterministic communication complexity with few witnesses
• Hellinger volume and number-on-the-forehead communication complexity
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Automata, Languages and Programming
• Hypergraphs, quasi-randomness, and conditions for regularity

This page was built for publication: Communication Complexity and Quasi Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5285941)