Alcalá alight

I'm now in Alcalá for EGC 2011. Last night I went out for stroll with my camera, sporting my new 'nifty fifty' 50mm f/1.8 lens. These are some shots I took.

New paper!

A few days ago I uploaded a new paper onto the arXiv. It was written with Attila Pór, Pavel Valtr and David Wood. In it we consider the connectivity of visibility graphs, which are graphs drawn on point sets in the plane where two points are joined by an edge if they 'see' each other - i.e. there is no point on the line between them.

One of my favourite results in the paper is a lemma which says that if you have two properly coloured plane graphs drawn with straight edges which are separated by a line, you can add an edge between them which is also properly coloured. This is not true if they aren't separated by a line. It's one of those things which seemed like it had to be true, but was quite tricky to prove. In the end Attila found a tricky proof. Perhaps there is a short proof using something like Borsuk Ulam (wild guess) but we couldn't find it.

Berlin visits, past and future

After my month in Lausanne last year I headed to Berlin again for about three weeks. That trip was self funded, but around that time I got the news that my supervisor and I had been successful in our application for some travel funding for a small cooperative project in Berlin and Melbourne. This will also allow me to visit again next year.

So now I am back in Berlin. I took the old MEL-DRW-SIN-FRA route with Jetstar on the first two legs, then Qantas. This was not so bad actually, especially since I got all the connections (I was on standby tickets) even though it was busy. Anyway, it's nice to be here again. My stay will last until mid August, with next week being spent in Spain at Los Encuentros de Geometría Computacional. I also hope to make a weekend trip to Belgium to see the 24hrs of Spa Francorchamps.

It was somewhat emotional last time seeing this city which I enjoy so much again after I had decided to move my studies back to Melbourne. Now I feel more relaxed because I know it will always be here, and I'll be back.

One of the first things I realised after getting here was that Melbourne maybe does have the edge food-wise (sorry Berliners!). About a week ago I had eaten at my favourite Indian restaurant in Melbourne, and when I arrived I went straight to one of my favourites here. I'm afraid it didn't compare well. At least eating out here is a lot cheaper than in Melbourne, especially with our high dollar.

On why one should be vegetarian and wear polyester shirts

I was reading an article in the newspaper about world population, and then had a look at this interesting BBC program. It addresses the problem that our species is capabale of exponential reproduction, but the Earth contains a finite amount of resources, so eventually (in fact soon) we must hit those limits. Water is one of the most important resources. We all know about water restrictions in Melbourne, but our water use extends far beyond what we take from the taps. For example, a cup of coffee takes about 120L to produce, and a can of beer 150L. Wow, that's quite a lot you say, and I thought I was an eco-friendly occasional coffee and beer drinker. Well, if you're a vegetarian who wears mainly polyester you are doing your bit, at least in a relative sense, because a cotton shirt takes 3000L, and a hamburger a massive 8000L of water to produce! Even if you buy a cotton shirt but wear it many times, you might be excused, but assuming you only eat your burger once, well, shame on you!

Edit: From another source I read that a kilo of beef takes 16000L of water to produce, so this is fairly close to the estimate above. But, the same source (actually a vegan propaganda flyer) said that it takes 2000L to make a kilo of soy. I hadn't really thought about how much it might be, but for me this makes meat's water usage seem not quite as bad as I thought. Especially if you eat chicken instead of beef at a claimed usage of 4000L per kilo. Of course, there are many other reasons to be vegetarian apart from saving water.

RapNews

RapNews is an awesome series of videos on YouTube from JuiceMedia describing current affairs with insightful and witty rhymes. I think these guys are amazing and their latest effort is one of the best.

Alfa AWUS036NH in Ubuntu 10.04

Since upgrading to 10.04 (from 9.04) my super duper Alfa AWUS036NH high power usb wifi dongle stopped working. I found this post very helpful. The problem seems to be that there are now two drivers which conflict. Apparently the rt2870sta module is for normal use, while rt2800usb is for packet injection. Most of us don't want to do that, so the solution is to blacklist rt2800usb in /etc/modprobe.d/blacklist.conf and thus only use rt2870sta.

Note however that this particular card uses the Ralink rt3070 chipset. The rt2870sta driver works (it is presumably meant for the rt2870 chipset), but maybe there is a more appropriate driver floating around. You'd have to install it manually if it exists. I'm just happy that the card works (including with WPA2 security).

What if P=NP?

Here is a nice (and tricky) problem that was posed in a computer science seminar that I am attending. It comes courtesy of Shir Peled.

Suppose you know that P=NP but don't know any polynomial time algorithms for NP-complete problems. Describe a polynomial time algorithm for SAT (or any NP-complete problem).

It may sound like a wierd question, but it does have a good answer. I will post the answer in a few days in case you want to try for yourself first.

Answer coming soon...

.
.
.

So now for the answer. It turns out that this was an unintentional April fool's joke. I didn't state the problem exactly as I should have. To see why, let's look at the solution.

You start by enumerating all Turing machines as a list of strings which encode their behaviour. Since P=NP, somewhere in this list there is a polynomial time machine that solves your problem and prints out the certificate for yes instances of the problem in polynomial time. You then proceed as follows:

• Run Machine 1 (M1) for its first step.
• Run M2 for its first step, then M1 for its second step.
• Run M3 for its first step, M2 for its second step, then M1 for its third step,
• and so on.

After each step you run, if the machine halts, check (in polynomial time) if its output is a certificate for your instance. If your machine is the kth one in the list, its running time is p(n), and it takes q(n) steps to check a certificate, then this algorithm will find certificates for yes instances in time less than k^2 * p(n)^2 * q(n).

The problem arises when we consider what happens with no instances. Since there is no polynomial size certificate for non-membership of an NP language, we can't expect our machine to print one out. In fact, we know of no method in this case. The original question should have been:

Suppose you know that P=NP but don't know any polynomial time algorithms for NP-complete problems. Describe an algorithm for SAT (or any NP-complete problem) which accepts yes instances in polynomial time, and behaves arbitrarily on no instances.

Shir tells me the following regarding this problem:

This formulation is taken from Scott Aaronson's blog, and is presented in the last exercise here, although the legend I know claims it originally is an exam question that Ely Porat gave to his students.