Further Topics

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

[Schulman 1992, Schulman 1993] present a variant of the two-party model, in which Alice and Bob are communicating using a noisy channel. That is, each bit that is sent by either Alice of Bob is flipped with some probability λ < 1/2 (which is independent from what happens in other transmissions). Say, a player may send the bit 0 but the other player will receive 1. The question is what is the communication complexity of computing a function f in such a model.
BibTeX
@inproceedings{kushilevitz1996further,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{Further Topics}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.015},
}

Loading related content...

Figure