Tuesday, July 18, 2006

Complexity Day 1

The Complexity Conference got underway yesterday with an invited talk by Pavel Pudlak on the connections of Gödel's work and computational complexity. Kurt Gödel was in 1906 is what is now Brno in the Czech Republic.

The next talk "Polynomial Identity Testing For Depth 3 Circuits" by Neeraj Kayal and Nitin Saxena is the first paper in Complexity history to win both the best paper and best student paper awards. The main result showed how to deterministically check whether an algebraic circuit was identically zero when the circuit has depth 3 with bounded fan-in on the top gate. Their advisor Manindra Agrawal was program committee chair but he did take the proper precautions in the discussions of the awards.

We had a reception last night at the Michna Palace in Prague. One young student remarked how one must be the smartest person in the world to prove new theorems. Not at all true. We have different backgrounds, different strengths, different experiences, different views on complexity that sets a situation where I can prove something that someone else would struggle with while they can prove something I would never find. Even if you have a similar background to someone "smarter than you", they don't have time to work on every problem so you can find good ones to work on your own.

Most of all my advice is to not worry about others and just work on your own. Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun.

3 comments:

  1. you can likely make more money doing something else that isn't fun.

    you can say that again...

    ReplyDelete
  2. Most of all my advice is to not worry about others and just work on your own. Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun.

    This is excellent advice Lance! After five years as a graduate student, I have learnt exactly what you said.

    I do wish that you use your blog entries more often to give such pieces of wisdom to new graduate students.

    ReplyDelete
  3. Poeple tend to relate new exotic theorems with the author's brilliance. I didn't know about Manindra Agrawal or about Kayal and Saxena before "Primes is in P" era. But sometimes when a graduate student's months of work becomes fruitless, he or she tends to think like that.

    Not everybody is Lance Fortnow or does he have an anecdote involving himself in such frustration?

    ReplyDelete