搜索结果: 1-4 共查到“理学 communication complexity”相关记录4条 . 查询时间(0.116 秒)
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...
Randomized Communication Complexity for Linear Algebra Problems over Finite Fields
communication complexity streaming, matrix singularity determinant
2012/12/3
Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger first considered this problem in the communication complexity model, in which Alice holds the first half of ...
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
Optimal Lower Bound Communication Complexity Gap-Hamming-Distance
2010/12/15
We prove an optimal W(n) lower bound on the randomized communication complexity of the much-studied GAP-HAMMING-DISTANCE problem. As a consequence, we obtain essentially optimal multi-pass space lower...
Non-locality distillation and post-quantum theories with trivial communication complexity
Non-locality distillation post-quantum theories trivial communication complexity
2010/4/9
We first present a protocol for deterministically distilling non-locality, building upon a recent result of Forster et al. [Phys. Rev. Lett. 102, 120401 (2009)]. Our protocol, which is optimal for two...
