搜索结果: 1-5 共查到“信息与通信工程 communication complexity”相关记录5条 . 查询时间(0.078 秒)
Average and Randomized Communication Complexity
Average Randomized Communication Complexity
2015/8/14
The communication complexity of a two-variable function f(x, y) is the number of information bits two communicators need to exchange to compute f when, initially, each knows only one of the variables....
Communication Complexity of Computing the Hamming Distance
communication complexity randomized protocol Hamming distance combinatorial
2015/8/14
Let x, y {0, 1} n. Persons A and B are given x and y respectively. They communicate in order that both find the Hamming Distance d(x,y). Three communication models, viz, deterministic, e-error and e-r...
COMMUNICATION COMPLEXITY OF COMPUTING THE HAMMING DISTANCE
communication complexity randomized protocol Hamming distance combinatorial extremal problem
2015/8/12
Let x, y {0, 1} n. Persons A and B are given x and y respectively. They communicate in order that both find the Hamming Distance d(x,y). Three communication models, viz, deterministic, e-error and e-r...
Streaming and Communication Complexity of Clique Approximation
Streaming Communication Complexity Clique Approximation
2012/6/13
We consider the classic clique (or, equivalently, the independent set) problem in two settings. In the streaming model, edges are given one by one in an adversarial order, and the algorithm aims to ou...
Property Testing Lower Bounds Via Communication Complexity
Property Testing Communication Complexity
2011/6/8
We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a
simple scheme for reducing communicatio...