Communication Complexity and Quasi Randomness

DOI10.1137/0406009MaRDI QIDQ5285941zbMATH OpenOpenAlexFDO

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

(23)

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

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)