Talk - Problem Solving Without Ansibles -- An Introduction to Communication Complexity
05 Mar 2021 - Tags: my-talks
Wow, two talk posts in one day! Thankfully the actual talks were a week apart!
Earlier today I gave another talk in the grad student seminar here at UCR. I wanted to break out of my logician mold a little bit, and so I decided to talk about a result which absolutely blew my mind when I first saw it: the (public coin) randomized communication complexity of equality is $O(1)$ for any fixed error tolerance $\epsilon$!
Since communication complexity is all about measuring the number of messages you send, I thought a fun framing device would be to imagine Alyss and Bob on separate planets. If they’re very far from each other, but they each have the computational power of an entire planet at their disposal, then it makes sense to measure communication as the limiting factor in their computation. This was in part inspired by Ryan O’Donnell’s excellent videogame themed talk (here), and indeed I tried to make my slides in google slides instead of beamer as an homage to him.
It definitely had advantages and disadvantages, but I liked a lot of the flexibility it offers. I think he does his in powerpoint, which might solve some of my bigger gripes. Notably drawing on the slides directly was impossible (because any time you release your pen, the scribble tool closes itself… that really needs a rethink on google’s end), so I had to do all the handwriting in gimp, then insert the writing as an image in google slides. This was annoying at first, but I gradually got into the flow of it. The most damning problem was how annoying it is to write mathematical symbols. Every single $\epsilon$ gave me a headache, and my entire browser lagged anytime the symbols menu was open. I know there are some add-ons which might make this easier, but nothing can beat a raw latex engine. In a more technical talk, I don’t think I could have possibly made the slides in this way.
All in all, I was really pleased with how the talk went, though! I think it’s an interesting enough topic to stand on its own, and it was fun getting to evangleize computer science to a crowd of mathematicians. CMU’s math department obviously worked quite closely with its CS department, and I forget sometimes that that isn’t the norm. I knew going into the talk that I wanted to spend some time talking about an interpretation of this using error-correcting codes (Hamming Codes in particular), but I ended up scrapping it and not writing the slides for it. In hindsight, I should have just made the slides, because as soon as someone asked a question that even hinted at this idea, I pounced on it and went on a mild tangent. I suspect I lost a lot of people during that, and it would have been a lot easier to retain them if I’d just organized the big ideas into slides. Oh well, I’m not going to fault past my too much for their laziness.
All in all, I really enjoyed giving this talk, and it seemed like the audience really enjoyed watching it. This was almost certainly due to the influence of Ryan’s lecturing style, and anyone familiar with his (excellent) “Theorist’s Toolkit” lectures (which I reference in the talk, and which you can find here) will recognize his impact.
With that out of the way, here are the things:
Problem Solving Without Ansibles: An Introduction to Communication Complexity
In the world of Science Fiction, an “ansible” is a device that allows for faster-than-light communication. Without ansibles, interstellar travel puts an interesting constraint on computation. If two planets want to collaborate on solving a problem, the obstruction will likely not be the computation that either planet does individually. Instead, what matters is the Communication Complexity which tracks the amount of messages the planets have to send each other to solve their problem. In this talk we will solve a prototypical problem in communication complexity. But be warned: the answer may surprise you!
You can find the slides here