CRM-Fields Lecture at University of Toronto

May 13, 2008
Jason Ernst
No Comments

Categories: Computer Science, Miscellaneous

Tags: Allan, Award, Borodin, CRM, Distinguished, Fields, Lecture, Mathematics, Toronto, University

About a week and a half ago I had the opportunity to attend a CRM-Fields Prize lecture by Allan Borodin at the University of Toronto. An audio recording of the lecture is available here:

http://www.fields.utoronto.ca/audio/07-08/crm-fields-pims/borodin/

His lecture was quite interesting and there was a really good turnout, the room was packed. The talk was entitled: Understanding Simple Algorithms: Towards a More Systemic Study of Algorithms. One funny portion of the lecture is where he compares the idea of an algorithm to the definition of profanity by the United States courts. Of course while I listened I tried to figure out ways in which I could use the ideas in his talk in my own research.

The part of the lecture that stood out to me in this respect were the multiple pass algorithms. Perhaps this approach could be used in Wireless Mesh Networks research for making routing decisions. I’m quite sure whether this approach would be fast enough to make quick routing decisions but it could be worth a try when I manage to get some time. He mentions that this approach may be used in scheduling which is partially what I’m interested in right now since I’m working with fair scheduling and load balancing in Wireless Mesh Networks (WMNs).

In general the talk gave a good background on algorithms and in particular greedy algorithms. Allan mentions how its very difficult for us to even define what a greedy algorithm is. In one situation a greedy algorithm can be very different than another situation. He talks about how you can look at what we can’t do with algorithms to figure out what we can do with them. Furthermore, in some situations we can’t even tell what we can and cannot do. Allan then went on to give alternative approaches to solving common problems such as dynamic programming, multi-pass algorithms etc.

The main point of the lecture was a framework that he proposes that uses an adversarial game to evaluate the algorithm. The framework allows us to evaluate an algorithm without having to worry about the P-NP complete problem. I guess the best way to figure out what it is about is to listen to Dr. Borodin himself via the link provided in the first bit of this.