The Communication Complexity of Correlation

By P. Harsha, Rahul Jain, David A. McAllester, J. Radhakrishnan. 2007

223 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sergey Levine
2. Jonathan Ho
3. Pieter Abbeel
4. Stefano Ermon
5. Chelsea Finn
6. Ruslan Salakhutdinov
7. Mohammad Norouzi
8. Yoshua Bengio

In Computational Theory and Mathematics

1. José Miguel Hernández-Lobato
2. Pieter Abbeel
3. Robert Peharz
4. Jonathan Ho
5. Marton Havasi
6. Sergey Levine
7. Jan Peters
8. Peter I. Frazier

In Information Theory

1. José Miguel Hernández-Lobato
2. Pieter Abbeel
3. Robert Peharz
4. Jonathan Ho
5. Marton Havasi

Citations in the corpus

• Denoising Diffusion Probabilistic Models (2020, background): “(5): see Algorithms 3 and 4, which assume access to a procedure, such as minimal random coding [19, 20], that can transmit a sample x ∼ q(x) using approximately DKL(q(x) ‖ p(x)) bits on average for any distributions p and q, for which only p is available to the receiver beforehand.”
• Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters (2018, methodology): “While Harsha et al. (2010) provide a constructive proof using a variant of rejection sampling (see Appendix A), this algorithm is in fact intractable, because it requires keeping track of the acceptance probabilities over the whole sample domain.”