Communication with Contextual Uncertainty by Komargodski, Ilan, Kothari, Pravesh K, Sudan, Madhu, Kothari, Pravesh K., Ghazi, Badih

“…Namely, we show that if g has a communication protocol with complexity k in the standard setting and the mutual information between X and Y is I, then g has a one-way communication protocol with complexity O((1+I)⋅2[superscript k]) in the uncertain setting. …”
Get full text
Get full text

Detecting component changes at run time with behavior models by Mocci, Andrea, Sangiorgio, Mario

“…Finally, we present a case study to validate the effectiveness of the approach in component change detection for a component that implements a complex, real communication protocol.…”
Get full text

Efficient Semantic Communication via Compatible Beliefs by Juba, Brendan Andrew, Sudan, Madhu

“…In previous works, Juba and Sudan [1] and Goldreich, Juba and Sudan [2] considered the idea of “semantic communication”, wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented and the user could sense progress towards the goal (or verify when it has been achieved), then meaningful communication is possible, in that the user's goal can be achieved whenever the server is helpful. …”
Get full text

Compression without a common prior: An information-theoretic justification for ambiguity in language by Juba, Brendan Andrew, Kalai, Adam Tauman, Khanna, Sanjeev, Sudan, Madhu

“…The resulting compression scheme resembles natural language to a far greater extent than existing digital communication protocols. We also use information theory to justify why ambiguity is necessary for the purpose of compression.…”
Get full text

AirShare: Distributed coherent transmission made seamless by Pant, Mondira, Abari, Omid, Rahul, Hariharan Shankar, Katabi, Dina

“…Distributed coherent transmission is necessary for a variety of high-gain communication protocols such as distributed MIMO and creating codes over the air. …”
Get full text
Get full text

The Computational Hardness of Estimating Edit Distance by Andoni, Alexandr, Krauthgamer, Robert

“…By excluding low-communication protocols for edit distance, we rule out a strictly richer class of algorithms than previous results. …”
Get full text