CiteseerX

Rather quietly, Citeseer appears to have undergone an upgrade (at least an alpha-level one). The new CiteseerX allows you to create collections, associate tags with papers, and has a generally snazzier interface. Whether it solves the problems of the old citeseer (constant crashing, almost laughably bad bibtex entries) remains to be seen.

On interview puzzles

Michael Mitzenmacher got hammered over at the complexity blog for trying to argue against the 'interview puzzle' style of interviewing so in vogue at places like Google, Microsoft and others.

Here's PhDComics' take on it:



I should add that I've been collecting questions that job-seekers are asked on such interviews.

The Joys of NAE-SAT

(ed: the point of this post will be completely lost on you if you don't often prove NP-Completeness results)

When all else fails, the "standard" way of proving a problem NP-hard is to go back to the basics, i.e 3SAT. One particularly quirky variant that I quite enjoy is NAE-SAT:

As usual, you're given an instance of satisfiability with clauses and variables, and you want to check if there's a satisfying instance. In NAE-SAT, the extra catch is that in no clause are you allowed to have all literals set to TRUE. Since no clause can have all literals set to FALSE, you get the name 'Not-All-Equal-SAT', or NAE-SAT.

Like SAT, NAE-SAT is NP-Complete, and remains so if you restrict clauses to containing 3 literals (i.e NAE-3SAT). Other interesting properties:

• NAE-3SAT is still NP-complete in its monotone variant (i.e if all variables appear unnegated). This is in contrast to SAT, which is trivial in that case. This property is particularly handy if you don't want to deal with how to ensure consistency between a variable and its negation when making a gadget.
• If X is a satisfying assignment for NAE-SAT, then so is X' (the complement of X). This is again because of the NAE-property. A clause that's satisfied with one literal becomes one that's satisfied with two literals, and so on. Since no clause has all three literals set to TRUE, no clause becomes unsatisfied. This is useful because when you assume that the problem has a satisfying instance, you have two instances you can use (we used this trick in a paper a while back).
• Unusually, and unlike other SAT variants, Planar-NAE-SAT is in P. This is a surprising result due to Bernard Moret, and prevents us from using NAE-SAT for many geometric problems where planarity is a useful tool (but if you can handle crossings, you're ok).
  

Anyone for a paean to ONE-in-THREE-SAT ?

David Gale, 1921-2008

Via Michael Trick comes the news that David Gale has died. To us CS folks, he's probably best known for the Gale-Shapely stable marriage algorithm (that has controlled the lives of thousands of medical interns since - talk about impact !), and the Gale Transform in projective geometry.

Apart from all of that, he was also a tremendously influential economist and expert in optimization. His obituary has much more.