In the wake of coming across my network and matching notes, where the 28 year old me taught the 50 year old me some things I never realized I knew, in a way that leaves (the 50 year old) me breathless (at least about the amount of time the 28 year old me had), I was delighted to see a new survey (published in the Communications of the ACM, no less) about complexity and voting systems that says some very nice things about the 28 year old me. The article, written by Piotr Faliszewski, Edith Hemaspaandra, and Lane Hemaspaandra looks at elections and the well known issue of manipulation of elections by giving untruthful representations of one’s preferences. The authors survey approaches that use computational complexity to protect elections:
This article is a nontechnical introduction to a startling approach to protecting elections: using computational complexity as a shield. This approach seeks to make the task of whoever is trying to affect the election computationally prohibitive. To better understand the cases in which such protection cannot be achieved, researchers in this area also spend much of their time working for the Dark Side: trying to build polynomial-time algorithms to attack election systems.
I have a particular fondness for this issue, since the 28 year old me (and his coauthors) wrote about this:
This complexity-based approach to protecting elections was pioneered in a stunning set of papers, about two decades ago, by Bartholdi, Orlin, Tovey, and Trick. The intellectual fire they lit smoldered for quite a while, but in recent years has burst into open flame.
Wow! Now that is a paragraph to send off to my Dean! I have written about how this approach was ignored for a long while, but is now pretty popular. It is great to see this coverage in an outlet like CACM.
The article goes on to survey this area, and has lots of nice things to say about those 20 year old papers (“seminal” (twice!), “striking insight”). And it makes a great case for all the work that has been done since, and issues going forward. Thanks Piotr, Edith, and Lane: I enjoyed the survey very much. And my Dad is visiting, and he too loved reading about what my coauthors and I had done.
From the 50 year old me to the 28 year old me: “That was pretty good work!” And, if I can speak for the 28 year old me: “Thanks! What are you doing now?” 50 year old me: “Hmmm….. can I tell you about sports scheduling? Blogging? Or perhaps I should introduce you to Alexander?”. 28 year old me: “Wasn’t I the one who met Ilona, with whom you have Alexander?” 50 year old me: “OK, we’ll split that one!”
Different phases, different measures. But I am impressed with the 28 year old me every time I run across him.