搜索结果: 1-6 共查到“communication complexity”相关记录6条 . 查询时间(0.124 秒)
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...
Communication Complexity and Coordination by Authority
Authority Complexity and Coordination
2015/7/31
We prove that the simplest communication allowing two players to coordinate on a course
of action is authority (letting one player choose an action). We also consider the case where
each player poss...
Streaming and Communication Complexity of Clique Approximation
Streaming Communication Complexity Clique Approximation
2012/12/4
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
2012/11/30
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...