Where duality helps

If you do geometry (or approximation algorithms, for that matter) long enough, it becomes second nature to flip between primal and dual space. Points become hyperplanes, convex hulls become envelopes, and so on.

Here's a question that has been puzzling me: What is a good example of a problem where flipping between primal and dual (or even just going from one to the other) is the key to its solution ? Now obviously, there are NP-hard problems that admit a primal-dual solution, where by definition we need the dual space. I don't mean these kinds of problems.

I'm merely wondering if there is a relatively simple problem with a relatively simple solution that would be hard to explain without duality. The easiest that comes to mind is how the complexity of the convex hull in 3D is linear (because the complexity of the lower envelope in 3D is linear). Another potential example is the rotating calipers method for finding diameter/width etc: it can be much easier to see what's going on in the dual space.

Categories:

• research

Windows and Linux, side by side

Captain's log, Sector 43, 3rd Quadrant, HELL. Temperature, -19 F:

Microsoft Corp. on Monday said it is teaming up with Linux supplier XenSource to allow computers to run the upcoming version of Microsoft's Windows server operating system on computers that are simultaneously running Linux software.

In the latest sign that it is dropping its resistance to Linux, Microsoft of Redmond, Washington is teaming up with Palo Alto, California-based XenSource to compete with VMware, now the biggest supplier of so-called ``virtualization'' software.

Categories:

• miscellaneous

We don't need no stinkin' publication count.

Presented for contemplation: Richard Feynman wrote only 37 research papers.

Categories:

• miscellaneous

Visa problems when travelling to the US ?

John Langford advertises an effort to document cases of visa problems for researchers trying to enter the US.

A serious effort is under way to raise this as in issue in need of fixing. Over the long term, effectively driving research conferences to locate outside of the US seems an unwise policy. Robert Schapire is planning to talk to a congressman. Sally Goldman suggested putting together a list of problem cases, and Phil Long setup an email address immigration.and.confs@gmail.com to collect them.

If you (or someone you know) has had insurmountable difficulties reaching a conference in the US, please send an email with:

Name:
Email address:
Conference:
Difficulty:
Details: (be brief please)

We expect most of the problem cases are students, so don’t be shy.

I'll second that. DON'T BE SHY. Efforts like this can actually work, and what makes them happen is access to the right people, and a good set of cases to fight for. The more cases there are (and all of us know of at least a few), the more powerful an argument we have. So please send mail to the above address.

Categories:

• immigration

7 blasts in Bombay

Developing...

all blasts along the Western Railway, in first-class compartments during the evening rush hour (around 1830). Death tolls are unconfirmed, but expected to be high. Mumbai Help is the central information source right now.

EurekaUK: Great discoveres coming out of Britain in the last 50 years.

An interesting list, and this item was interesting:

Section four: Discoveries for the digital age

Manchester: birth of the first working computer
Two University of Manchester scientists, Freddie Williams and Tom Kilburn, are credited with running the world's first stored program computer.

I grew up thinking that one of ENIAC/EDSAC/EDVAC was the first stored-program computer. It turns out that ENIAC came close to being one, but didn't. There's more info at Wikipedia. According to Wikipedia, the Manchester "Baby" was developed in 1948, which was more than 50 years ago :)

Categories:

• history

SODA submits: stunning drop

Muthu announces that there were 380 submissions at SODA this year. This is a stunning drop: last year, some 450 were submitted, and the year before, 487 (although many of those were short papers). This is the lowest submission count since 2002, coinciding with a much-larger-than-normal increase in the committee size.

Categories:

• conferences
• soda