Reviews

A couple of times I got annoyed by obnoxious reviewers who clearly didn't spend enough time to understand the paper. That made me wonder (1) if others feel annoyed by bad reviews and (2) if others feel annoyed by my reviews.

The answer to (1) is mixed: some are annoyed and some take it better.

As for (2), I now know that at least not all authors reviewed by me are annoyed: Today I've been contacted by a PC chair because the authors specifically wanted to send their thanks for my review.

P ≠ NP?

According to a dream that just ended it can be solved by applying Solomon's criterion to reduce it to Sauron's problem.

Sums of sets

Two more programming puzzles.

You want to partition sqrt(1), sqrt(2), ..., sqrt(n) into two sets that minimize the difference of the sums. What's the best complexity you can get?

And one via David Eppstein. (Don't look unless you want a big hint.) "Let S be a set (or multiset) of positive integers. Describe an efficient algorithm for finding the smallest positive integer x such that x is not the sum of some subset of S."

ETAPS 2008, part 0

First highlight: One evening Rustan entertained us with lots of puzzles. We managed to solve most (all?) of the ones we discussed. Here's the one I thought was the hardest.

Next I'll tell you how to generate invariants with universal quantifiers by using an interpolating prover, straight from the "best paper" at TACAS.

And now some off topic stuff.

Since we are talking about puzzles, here's another one I saw recently. It was previously featured on xkcd and it is also featured by one of the toilets in the CASL. It didn't excite me before I saw the (intentionally) wrong solution of Terence Tao. The fact that the error is so subtle made me think that I got the correct answer in the first place by accident :)

Unrelated: Any ideas what I should do with my new Google backed (home) page?

Web 2.0: 10 minutes braindump

Idiot: a person who incessantly argues about unimportant issues. Such as: Is Web 2.0 a buzzword or a profound new vision? Well, establishing beyond doubt that Web 2.0 is indeed a buzzword would be just about as useful as establishing that it is a stroprantzer.

Let's say that we want to make Internet more useful. Let's assume that existing websites have various degrees of usefulness and that users favor the useful ones. Question: Can we find a good predictor for the usefulness (and hence popularity) of a site? My wife proposed: Useful sites offer services based on information gathered from the users. Proof by examples:

1. YouTube offers
   • search for video-clips
   • video-clips
   • lists of similar video-clips
   based on
   • video-clips submitted by users
   • comments submitted by users
   • users' navigation patterns
2. EBay offers
   • cheap products
   • buyers for stuff that your friends don't want
   based on
   • what users want to buy/sell
3. Amazon offers
   • book recommendations
   • books
   based on
   • what users buy
   • second-hand books offered for sale by users
4. IMDB offers
   • movie recommendations
   • movie ratings
   based on
   • user ratings and comments
5. Google offers
   • search
   based on
   • stuff users put on the web

All these sites make it very easy for users to offer data: to tell YouTube what videos are similar you just browse the site, to put a web-page on Google you do… nothing.

Could someone inclined to make money do so based on these observations? No idea, but here's how I would start: What types of sites I know that do not follow the description above? Let's see:

• home-pages of scientists
• web-sites that present private accomodations in one area ("pensiuni" in Romania, B&B in Ireland and UK)
• booking of airplane tickets
• local renting (Ireland has Daft, but other place like Romania don't)
• local movies (per city? country?)

Now let's say we want to make a web-site (2.0!) for movies playing in Bucharest (to replace the horrible thing available now). We should:

• have a search box: people expect it
• let users comment: we can use that to improve the search!
• secretly use external data sources to boot-strap your web-site, but don't say so: write scripts to fetch data from existing web-sites, make deals with off-the-web information providers and so on (BTW, secretly means that you don't tell the users how you get the data, in case you had doubts about the meaning :P)
• give recommendations and ratings
• give comprehensive data about playing times
• make it very very easy for users to provide information: movie ratings, comments, playing times (but, at least initially, do not rely only on them — see the point on using external data sources)

Above all, make it work flawlessly and fast (even test from dumb operating systems like Windows!) and have a very very simple user interface (a person that is >50 should find it easy!).

Ah! And, it may give you a head start if you don't mention to others what you are doing until you launch a beta. (If you try this method and make money then don't forget to send me some royalties.)