[Computational Complexity] 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.
Posted by Lance to Computational Complexity at 7/18/2006 02:24:00 AM
- I arrived at the Institut Henri Poincaré in time to catch the last half of Ryan Williams giving a talk on our paper with Rahul Santhanam. I missed the first set of talks including Mark Braverman's Poly-logarithmic independence fools AC0 circuits. To no one's surprise Braverman won the best paper award for this work. The Ronald V. Book Prize for Best Student Paper went to Akitoshi Kawamura for his paper Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete.A good turn out, about a hundred for the conference including many notables such as Steve Cook, Manindra Agrawal and of course Bill Gasarch. Eric Allender is here so we are now both at 24 and counting for perfect attendance at complexity conferences. Great to see many friends, colleagues and former students including Sophie Laplante, the main local organizer. Something about Paris draws people to the conference.With my jet lag I realized I would just snooze through any afternoon talk so I had a pleasant time talking research in the Jardins de Luxembourg (near the conference site). Now I'm off to bed and hopefully well rested for day 2.
Posted By Lance to Computational Complexity at 7/15/2009 01:14:00 PM