Communication Complexity and Quasi Randomness

descriptionPublicationkeyboard_double_arrow_right Article 01 Feb 1993 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Discrete Mathematics, volume 6, pages 110-123 (issn: 0895-4801, eissn: 1095-7146,

Copyright policy )

Authors: Fan R. K. Chung; Prasad Tetali;

doi: 10.1137/0406009

Communication Complexity and Quasi Randomness

- Summary
- Subjects
- Metrics

Abstract

Summary: The multiparty communication complexity concerns the least number of bits that must be exchanged among a number of players to collaboratively compute a Boolean function \(f(x_ 1,\dots,x_ k)\), while each player knows at most \(t\) inputs for some fixed \(t

Keywords

Combinatorial probability, Random graphs (graph-theoretic aspects), hypergraph, Hypergraphs, lower bounds, Switching theory, application of Boolean algebra; Boolean functions, Turing machines and related notions, Boolean function, discrepancy, multiparty protocols, quasi randomness, multiparty communication complexity

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	32
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average