Communication Complexity and Quasi Randomness
DOI10.1137/0406009zbMATH Open0771.05073OpenAlexW2044575164MaRDI QIDQ5285941FDOQ5285941
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
Recommendations
discrepancylower boundsBoolean functionhypergraphmultiparty communication complexitymultiparty protocolsquasi randomness
Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Hypergraphs (05C65) Turing machines and related notions (03D10)
Cited In (21)
- 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
- Communication complexity of key agreement on small ranges
- Hellinger volume and number-on-the-forehead communication complexity
- Interleaved Group Products
- Communication and Randomness Lower Bounds for Secure Computation
- Pseudorandom functions: three decades later
- Quasi-random subsets of \(\mathbb{Z}_ n\)
- 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
- Simultaneous multiparty communication protocols for composed functions
- Hadamard tensors and lower bounds on multiparty communication complexity
- 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)
