Computational Aspects of Communication Amid Uncertainty
Başlık:
Computational Aspects of Communication Amid Uncertainty
Yazar:
Ghazi, Badih, author.
Yazar Ek Girişi:
Genel Not:
Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
Advisors: Ronitt Rubinfeld; Madhu Sudan.
Özet:
This thesis focuses on the role of uncertainty in communication and effective (computational) methods to overcome uncertainty. A classical form of uncertainty arises from errors introduced by the communication channel but uncertainty can arise in many other ways if the communicating players do not completely know (or understand) each other. For example, it can occur as mismatches in the shared randomness used by the distributed agents, or as ambiguity in the shared context or goal of the communication. We study many modern models of uncertainty, some of which have been considered in the literature but are not well-understood, while others are introduced in this thesis:
Uncertainty in Shared Randomness • We study common randomness and secret key generation. In common randomness generation, two players are given access to correlated randomness and are required to agree on pure random bits while minimizing communication and maximizing agreement probability. Secret key generation refers to the setup where, in addition, the generated random key is required to be secure against any eavesdropper. These setups are of significant importance in information theory and cryptography. We obtain the first explicit and sample-efficient schemes with the optimal trade-offs between communication, agreement probability and entropy of generated common random bits, in the one-way communication setting.
• We obtain the first decidability result for the computational problem of the non-interactive simulation of joint distributions, which asks whether two parties can convert independent identically distributed samples from a given source of correlation into another desired form of correlation. This class of problems has been well-studied in information theory and its computational complexity has been wide open.
Uncertainty in Goal of Communication • We introduce a model for communication with functional uncertainty. In this setup, we consider the classical model of communication complexity of Yao, and study how this complexity changes if the function being computed is not completely known to both players. This forms a mathematical analogue of a natural situation in human communication: Communicating players do not a priori know what the goal of communication is. We design efficient protocols for dealing with uncertainty in this model in a broad setting. Our solution relies on public random coins being shared by the communicating players. We also study the question of relaxing this requirement and present several results answering different aspects of this question.
Uncertainty in Prior Distribution • We study data compression in a distributed setting where several players observe messages from an unknown distribution, which they wish to encode, communicate and decode. In this setup, we design and analyze a simple, decentralized and efficient protocol.
In this thesis, we study these various forms of uncertainty, and provide novel solutions using tools from various areas of theoretical computer science, information theory and mathematics. (Copies available exclusively from MIT Libraries, libraries.mit.edu/docs - docs mit.edu).
Notlar:
School code: 0753
Konu Başlığı:
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(687406.1) | 687406-1001 | Proquest E-Tez Koleksiyonu | Arıyor... |
On Order
Liste seç
Bunu varsayılan liste yap.
Öğeler başarıyla eklendi
Öğeler eklenirken hata oldu. Lütfen tekrar deneyiniz.
:
Select An Item
Data usage warning: You will receive one text message for each title you selected.
Standard text messaging rates apply.