Tag Archives: Talk

B. Liskov on the Power of Abstraction

Posted by on May 30th, 2011 Comments Off

Barbara Liskov giving her Turing lecture

Last week, Barbara Liskov visited Kaiserslautern and gave her talk On the Power of Abstraction. I had known her from the substitution principle named after her1 and taught to every computer scientist and programmer, but she is far more distinguished than that: Barbara Liskov is an ACM Fellow, holds the ACM Turing Award and the IEEE John von Neumann Medal and a couple of other awards, telltale of her influence on the field.

The talk she gave is actually her Turing lecture, obligatory for Turing awardees. The room was so packed that quite some people had to remain standing, and it was worthwhile to have come. You can watch the lecture—in another instance—in full here. For me as a CS novice, the lecture is a small time travel machine to the seventies: Barbara talks about the history of how abstract datatypes and related concepts came to be. As someone who grew up with languages like Java, it is hard to imagine a world where all programming there is is literally done on assembler level. So, lots of the material presented should feel trivial to the modern mind, but Barbara manages to instill the spirit of the time into her listeners. After her talk, you know why she got awards for things you take for granted today.

Since the lecture itself can be watched online, I just want to share my favorite quotes and anecdotes I wrote down during the talk; I hope I am not misquoting.

[Barbara] did not apply at MIT because she did not want to be a nerd.

I have no idea how I got that idea. [...] It was ready to be discovered.

You never need optimal performance, you need good-enough performance. [...] Programmers are far too hung up with performance.

There were no GOTOs because I believed Dijkstra.

It’s really just common sense.

Why did she get this award? Everybody knows this anyway!

Especially the last quote demonstrates, if unintentionally, the impact of Liskov’s and others’ work of that time. If something you conceive is considered common sense 30 years later, you really had a brilliant idea.

  1. She did not name it, of course. Apparently, she received an email in the 90′s by somebody asking her wether he got “her” principle right, surprising her She had not known that the principle had borne her name for years in the community. ↩

N. Misra on Polynomial Kernelization

Posted by on October 11th, 2010 Comments Off

Neeldhara Misra, PhD student from IMSc (Chennai, India), recently visited our department at Chalmers. I had the opportunity to attend her well-given talk about the occasional infeasibility of polynomial kernelization. I liked the ideas she presented so I want to share them; you can read her own summary and download her complete work on her website.

Idea of Kernelization

Kernelization is about formalising preprocessing for hard problems and figuring out what can and cannot be achieved. In particular, NP-complete problems are studied; for these problems no fast (i.e. with polynomial bound on runtime) algorithms have been found yet. The idea is to crunch down a given instance of size to a size that is manageable by — more or less — naive algorithms while preserving equivalence, that is the reduced instance should have a solution if and only if the original instance has one. The notion of manageability is captured by a problem and instance dependent parameter ; we say that we have a polynomial kernel if there is an equivalent problem whose size is bounded by a polynomial in (i.e. independent of ). If is small — which is often the case in practical scenarios — the kernel can be solved reasonably quickly. Of course, the reduction process should then also be fast. Remains to mention that has to be chosen wisely; only knowing at least an upper bound for enables useful kernelizations. Read more »