Intense conference

Jan 6: The last few days at the SODA 2009 conference has been an interesting and instructive experience. This was another world from what I had been used to in Beijing and at Duke. This was when mental abilities and mathematical prowess really mattered again, and I fell terribly short.

The day before my talk, while waiting for my roommate who made the hotel registration to show up so I can enter my room, I practiced my presentation a few times. I recorded myself using my computer and timed to ensure that I finished in 20 minutes. I found this helpful because it allowed me to hear my own stuttering and drawling, which I normally am fairly oblivious to, and I adjusted my pace at times and tried to keep the presentation professional. That night, I listened to a friend's advice and carefully selected my outfit: my best Dockers black slacks, my most expensive shirt from Reiss, my formal Rockport dress shoes and nice black socks. The morning before the talk, I got up early, showered, and in my attempt to be stylish, put on some hair wax. But the more I tried to shape it in front of the mirror, the more messed up it became. Fifteen minutes later, I realized I didn't have time to waste, so I let my hair alone, quickly brushed, got dressed, picked up my notebook, wore my name tag, put on my tailored coat, and confidently walked out the room. In the hallway, I looked again into a mirror, practiced smiling, and squeezed into a packed elevator 5 minutes before the morning session began.

But the talk itself felt anti-climatic. I think that I handled it fairly well, except when I was told I had 5 minutes left and became nervous and stuttered a bit, jumbling up the slide explaining the intuition behind our classification of states. But it didn't seem to matter. People clapped and continued discussing technical research tips. Later I listened to a presenter whom I thought was ridiculous--he kept up an exaggerated goofy and childish tone, making the presentation seems very unprofessional. When I commented to Matt, he said something that left a deep impression: it doesn't make a difference. Indeed, to a real researcher, only the content mattered, instead of how well the presenter spoke. Reflecting deeper, I think that in the past half year I have placed too much importance on appearances, instead of real substance; the smart people at the conference could look through my facade and see the emptiness inside.

There's another point that bothered me. In my first paper I actually came up with majority of the results, but in this one it was mostly my professor and his co-author. They worked very hard on this, pulling several all-nighters, while I did the bare minimum. Because this was a good paper, I did not want to claim credit that I do not deserve, so at the beginning of my talk I emphasized that the paper was mostly by the other two authors and I was simply an undergrad research assistant. After the talk some guy from Google came up to me and asked whether I really did none of the work. This seemed unfair at first because I did come up with some ideas, which although are not revolutionary, did prove to be key in the final argument. But before I spoke to defend myself, I thought about it further and realized that my professor hinted at those ideas as well. There's really no significant part of the paper that I can claim as mine: beside providing ideas, all I did is to clean up some proofs, rewrite some passages, and come up with trivial ancillary results which I wasn't even sure was included. Maybe I was a complete leecher after all.

Moreover, the conference cleared away the false security that I had enjoyed in my worth as a researcher. In my school studies, I have always done well and people around me say that I'm smart. Also, I've been fortunate to find a brilliant advisor who helped me publish 2 papers in respectable conferences. This had built up a cloud of vanity around me, making me feel that I'm essentially a PHD student and grad school would be a breeze. But this is all BS! Even the first-year grad students I talk to seem to have read all papers in their field in the past 10 years, and know all the techniques and who came up with them. What really set researchers apart is their ability to come up with problems, make conjectures, and think about problems for fun. This keeps their brains shape and quick. Compared to them I'm but an empty shell, knowing nothing and mentally dead. I have a lot to learn and a lot of catching up to do.

But this is to be expected. Research is like any other job, in order to create value I must put in the effort. There's no free lunch!

Here are just a few of the really cool talks I heard:
- Ratio Index: Goel et al. devise an approximation algorithm to the budgeted learning problem using what they call the ``ratio" index. My advisor had worked on this problem before and obtained a constant approximation through our usual technique of LP rounding. But the ``ratio" index can be computed for each arm in isolation and hence is much more practical. I should look into analogs of this for the bandit problems I've worked on.
- The ``follow the leader" approach for analyzing regret in bandit problems.
- Nonparametric Bayesian Modeling: Dr. Jordan from Berkeley explains his way of making Bayesian modeling nonparametric by making the parameters and parts of the hiearchial structuring something to be inferred as well. This is mathematically nice and has been implemented to improve state-of-the-art software for protein folding, document classification, image processing, language parsing, etc. So elegant math can transform into real, important applications! This is the style of research I want to do.
- Lifshits et al. approach the problem of similarity clustering with the insight that sometimes the similarity measure is not a metric. For example, if the similarity measure between two people is the # of common friends on facebook, then this does not need to satisfy the triangle inequality. They propose to discard the actual measure, but only preserve the comparison oracle: is B or C closer to A? Assuming that the ``closeness rank" measure they define loosely satisfy the triangle inequality, then they can efficiently produce a structure that allows greedy, near-optimal routing.
- Natural Algorithms: Chazelle uses the tools of computer science and solve an open question in theoretical ecology: the convergence of bird flocks. It's cool how as two flocks collide, the energy in the first ``eigenstate" disappear and the rest of the eigenstates "shift up." I need to learn linear algebra better. How he combines two independent fields is interesting, and his animations are cool!
- What are dictatorship tests, unique game hardness, DS sequences, self-concordant barriers, Dikin ellipsoids, nucleolus, Dilworth's theorem, Grothendieck's constant, 5-universal hashing, FPTAS, Tukey medians??? So much that I need to know...
- Demaine et al. showed probably the pretties idea I've seen at the conference. They defined this problem in plane geometry, and showed that it is equivalent to the old problem of finding the minimum operations needed to access a sequence of nodes in a BST, allowing for rotations. Their insights clarify the connection between many conjectures, prove some new results, and elucidates the rich structure in the analogy between the two problems. No wonder this guy became a professor at MIT when he was 20 and is now a 27 year old tenured professor!
- Volker Strassen: "the question is the most important; not the answer"
- Bansal et al. prove 3-approximation in an online speed scaling problem using this nice potential function. I should learn from how they systematically construct their potentials.
- Here's an almost philosophical question: If finding the Nash Equilibrium is intractable in polynomial time, can we really expect real markets to quickly converge to solutions?
- Martingales are cool. So much to absorb here...
- Brubaker's robust PCA seems to be what my office-mate needed for his project at D. E. Shaw.
- Yi and Zhang's online tracking algorithm through intersecting successive balls centered at medians is nice, resulting in a simple proof of the competitive ratio.
- Bansal and Chan's proof precluding the existence of O(1)-competitive algorithm for online weighted flow-time is nice. I'm amazed by how people can PROVE that an algorithm does NOT exist. Chan's presentation is funny. Russel Peters would have a lot of fun with his accent. lol.
- Angelopoulos' bijective analysis framework is interesting. The math looks rigorous and elegant.
- Babaioff et al's analysis of generalized secretary problems is cool. I should learn from their simple but powerful analysis techniques.
- Cohen's axiomatic approach to stream sampling is elegant and practical. AT&T actually implemented it and it works!

Wow, I ended up writing so much more than I planned... There's a lot of nice ideas to follow up and questions to think about. After all, if I'm going to grad school, I need to work much harder at research. No more slacking!