The world has been witnessing a massive surge in data accumulation, which, combined with the distributed nature of the data, necessitates efficient and robust methods for information transmission. The study of communication addresses diverse aspects of such transmission between different parties, and has become a powerful tool across a wide range of seemingly unrelated research fields.

In this dissertation, we first examine sublinear models, where algorithms for handling massive data are designed to minimize the usage of valuable computational resources. We study fundamental graph problems, such as MST, MIS, and Maximal Matching, for which celebrated multi-pass algorithms are known in streaming and distributed sketching settings. Using novel information theoretic techniques, we prove almost matching lower bounds for any number of passes.

Additionally, we explore how interaction can improve the robustness of communication. While the optimal noise resilience of one-way binary error correcting codes has long been known to be 1/4, we show how to achieve resilience beyond 1/4 by allowing a single short round of noisy communication from the receiver back to the sender. In the setting where the receiver’s feedback is noiseless, we characterize the resilience as a function of the number of feedback rounds.