Learning everyday
I recently wrote a general blog post on sharing knowledge. I ended it with an upbeat statement. I really feel lucky to have friends who enjoy sharing their knowledge and just learning in general.
This series on communication complexity is not one I journey alone but rather with one of those friends. My friend Leah is one of those friends who really loves learning and sharing. We decided to learn communication complexity together.
I am super excited about this journey. Learning is fun but learning together is 100x better.
We both purchased the following textbook: Communication Complexity: and Applications by Anup Rao and Amir Yehudayoff.
We plan to go through this slowly since we are both new to the subject. I hope to share some interesting insights here as wel progress through the textbook.
Leah is fantastic artist so hopefully I can squeeze some visuals off her iPad and onto these blog posts every once in a while.
During the time of writing this we are about 14 pages into the textbook. We skimmed the perliminaries section and figured we'd track back to it when necessary. The perliminaries are really just about math convention used in the book and some brush up on statistics and probability.
The main question the first 14 pages cover is: What is communication complexity and how can we build a model to analyze it.
Communication complexity is a way of analyzing how two (or more) parties can communicate with each other. Like always (imo) an example helps.
In classic communication complexity fashion we can imagine 2 parties: Alice & Bob.
Both Alice and Bob contain a set of 10 numbers where each number is between 1-100. The question they would like to figure out is, is there a number which they both have in their respective sets.
How many bits of info must Alice and Bob exchange before they can know for certain the answer?
What is the most "creative" scheme to achieve this type of communication?
These are the types of questions communication complexity deals with.