When does Bob deserve to be a co-author?

I have recently been reading Bill Gasarch's post about when Alice deserves to be a co-author. This is definitely a sensitive issue; just check the number of ANONYMOUS comments. I have recently found some advice that is more oriented towards faculty-student type of collaborations, but is perhaps also suitable in general. Check this link. Interestingly, it was a document written by Department of City and Regional Planning, University of Berkeley ...

Highland workshop on XML, Logic, and Automata

I'll be attending Highlands Workshop on XML, Logic, and Automata organized by Leonid from tomorrow until this Sunday. The venue is actually quite interesting: a small town in the Highlands called Grantown-on-spey. I'm just hoping that they have a grocery store :) I will give a presentation on recurrent reachability in regular model checking based on this paper. Anyway, I'll post a summary of the workshop later on this week.

Rahul Santhanam has joined Edinburgh

Rahul Santhanam, Lance Fortnow's ex PhD student, has recently joined Edinburgh's School of Informatics. Warm welcome to him!

Finite-variable hierarchy conjecture

It seems that Ben Rossman has resolved another long-standing open problem in finite model theory: finite-variable hierarchy conjecture. Loosely speaking, the conjecture is that over ordered graphs first-order logic with k+1 variable is more powerful than first-order logic with k variable. The problem is nicely summarized in Anuj Dawar's survey. Ben has shown that this hierarchy is strict. What was previously known is that (over ordered graphs) first-order logic with 3 variables is strictly more expressive than first-order logic with 2 variables, but it was not known whether first-order logic with 3 variables is less expressive than first-order logic with k variables, for every k > 3. Worse yet, it wasn't even known whether this hierarchy is strict. See Anuj Dawar's survey for further details.

I believe this is the third big open problems that Ben has resolved in this decade. Go Ben!

Restructuring logicomp

I'm thinking of restructuring my blogs. I've recently found that things have changed a lot since I started my break a year or so ago: Lance has retired from blogging, Andy D has started his new cool blog, and Luca Aceto has his blog. Ah ... also I'm having a lot of difficulty deciphering blogger's word verification mechanism.

Unfortunately, I've become really rusty with HTML and will have to start getting used to it again. Shocked with what a long break can do to one's dexterity ;) Anyway, I'll put all the new links some time soon.