Tuesday, May 23, 2006

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.

On a personal note, today I have lived as long as my father. Puts a real perspective on life.


  1. Lance,

    What's your opinion on the Fly America Act?


  2. I'm not quite of your generation, and *I* got that... in my undergraduate lab, we used to say "We secretly replaced words a_0 through a_n with folgers crystals." "I couldn't tell the difference, but I was vastly more awake!"

  3. I agree Lance ... I find most conference talks to be bad. If I want to understand a complex proof, I'll take a few hours or days and read the paper. Spend your 20 minutes or so in a talk for motivation, overview, and concepts.

  4. I am not sure.. How would you feel if
    most people are hanging out in the hallways and talking with other attendees while you are giving the talk?

  5. How would you feel if most people are hanging out in the hallways and talking with other attendees while you are giving the talk?

    What you rather have them under duress in your talk? People who care about the results will attend regardless, people who don't are welcome to chat outside rather than fall asleep in a talk. If you submitted your paper to the right conference there ought to be many participants interested in your talk anyhow.

  6. Except the hallways are very near to the rooms. There were some rooms reserved for discussion and stuff but not many people were using them. I guess there was no coffee there.