[Computational Complexity] Thoughts from STOC
I don't go to many talks at STOC, I prefer hanging out in the hallways and talking with other attendees. But the best talk I saw so far was the first, Atri Rudra gave an easy to follow overview of a his paper Explicit Capacity-Achieving List-Decodable Codes with Guruswami. Both student paper award winners also gave nice overviews of their technical results. Much better than trying to wow us with complicated formulas.
What were the folks in the hallways talking about? Worry about funding in the short term but cautious optimism a few years down the line. Some optimism on employment; many good places hired in theory this year and most students found postdoc, faculty or industrial positions. I didn't see many students scrambling for jobs. Last time STOC was in Seattle (1989) I was one of those scramblers.
Prabhakar Raghavan, a theorist who now heads Yahoo! Research, gave the first invited talk about some mathematical questions related to Yahoo. Prabhakar spent a considerable part of his talk on sponsored search, the bidding and ranking mechanisms for those who pay to be listed right of the search results. Yahoo currently uses a variant of second-price auctions that is non-truth telling and has some other flaws but is simple enough for people to understand how much they will pay. Google on the other hand use more complicated schemes with nicer properties but most if not all of its users don't really understand the bidding mechanism.
Russell Impagliazzo gave the other invited talk on pseudorandomness, his title slide containing a joke only my generation would get.
Let's secretly replace Al's coffee cup of random bits with pseudorandom bits and see if he notices.Russell's take-home message: Randomness does not help in algorithms but we can't prove it doesn't help until the circuit complexity people (like Russell) get on the ball and prove some good lower bounds.
- I haven't been to STOC/FOCS since FCRC in San Diego two years ago. Since then I dropped thirty pounds and got a haircut last week. Amazing how many people thought something looked different about me and asked about the haircut.
I missed the Valiant celebration but it brought a large number of senior theorists who don't often attend STOC/FOCS. I enjoyed seeing and talking with them. Still, despite a relatively easy to reach location (say compared with last year's Victoria), STOC only attracted about 260 attendees, nearly half students. We just don't get draw many non-local attendees who don't have papers in the conference. Though David Johnson told me he's attended every STOC since the early 70's.
I don't attend many talks at STOC, I prefer to hang in the hallways chatting with people, about research, politics, gossip and baseball. The talks I did attend usually had about five or so good minutes of motivation and results followed by technical details for experts in that particular area. That's probably the right way to give those talks but I was rarely one of those experts.