O'Rourke's Art Gallery book

Joe O'Rourke mentions that his classic on art gallery problems is now available for free online. Download it now ! And while you're at it, buy his book on folding (with Erik Demaine). I just bought the folding book (and have already assigned one class project from it).

Levels of hell (heaven?) when writing practically motivated theoretical papers

I was going to post this as a comment on Michael's post, but it started getting longer and longer.

The main question being discussed there is: how do you balance the theory and practical sides of your work effectively from a point of view of getting and keeping faculty jobs ? it's good to remember that not every problem is amenable to a joyous merge of theory and practice: There are levels of hell (heaven?) involved here, that go something like:

* prove fundamental new result, and this leads to breakthrough implementation for a problem people couldn't solve (this happens usually in an area relatively untouched by theory thus far, and can really make you famous) (I'd imagine RSA/Diffie-Helman fall in this category)
* Brand new result: leads to improvements in efficiency AND accuracy of known methods by orders of magnitude
* Brand new result: improves on efficiency OR accuracy of known methods, by orders of magnitude.

Below this line, you're unlikely to get a theory publication out of the contribution:

* Observation that known approaches (or derivations thereof) lead to improvements in efficiency AND/or accuracy by orders of magnitude
* New theory result, some improvements in efficiency AND accuracy

And here's where it gets positively hellish:
* mildly new theory result, reasonable improvement in efficiency and accuracy, but not orders of magnitude, and you go up against an entrenched, highly optimized heuristic (k-means, anyone ?)

At this point you really have to choose which you care about, the problem or the theory, and then branch out accordingly. Papers in this last realm are really difficult to publish anywhere, even when they nontrivially improve the state of the art.

ACM Fellows, 2008 edition

ACM has announced its Fellows for 2008. Familar names on the list include:

• Sanjeev Arora
• Ken Clarkson.
• Steve Cook
• Michel Goemans
• Ian Munro
• Madhu Sudan

In the related area of game theory, Xiaotie Deng and Tuomas Sandholm were honored as well. Congratulations to all the winners !

(HT: Michael Trick)

A "Green" conference...

(Update 2/17/09: Workshop dates changed to Apr 9-10)

Kirk Pruhs asks me to mention what I'll call the first "green" workshop of 2009:

Workshop on the Science of Power Management (Mar 26-27)

The rapidly increasing power consumption associated with information technology (IT) results in a myriad of adverse impacts including high utility costs, unsustainable thermal densities, poor space usage, and a substantial carbon footprint. In view of this, reducing IT power consumption has become a pressing priority at all levels of computer technology from semiconductor materials and processes all the way up to the design of entire data centers.

Although there is already significant research and development activity around power management in academia and industry, power remains a very difficult subject to deal with in a scientific and formal way. A grand challenge for the scientific community is to understand the trade-offs between power consumption and computability at a much more fundamental level. Ideally one would like to determine the limits of computability under power/thermal constraints, design systems that approach these limits and quantify corresponding performance tradeoffs.

This is a "NSF CFP generating workshop": the idea is for the workshop to generate material for a funding call. For more info, do contact Kirk, or Sandy Irani.

SODA news: American Association of Chiropractors in a deep funk...

As promised, there was no hard copy proceedings at the conference this year, causing spinal columns everywhere to heave a huge sigh of relief. What's even more amazing is that ALL the papers from the conference are online: I downloaded them all last night ! Bill Gasarch has this, and more on why he enjoyed SODA, which apparently disturbed Lance so much he had to snark in the post immediately after :)

p.s the comment linked above points out that Las Vegas was the "first choice" for SODA in 2010, even though Austin was the "realistic second" that ultimately won.

SODA location news

No Salt Lake City, alas: however,

SODA 2010 in Austin, Texas, and SODA 2011 in Paris, France (of course unless SIAM and SODA steering committee will change the outcome of the majority vote, what is most likely to happen, in which case it should be San Francisco)

Somehow, I can't see David Johnson the SODA steering committee agreeing on Paris.

Update: More on the vote: it was Paris (60), the Virgin Islands (!) (50), San Francisco (46) and SLC (44). Clearly, I should have attended SODA and brought a student with me :)

On a related note: Virgin Islands ? What, have we given up on Puerto Rico as the token 'ain't gonna happen in a million years' location ?

Update: see the comment by Luc Devroye for some pushback to my claim that VI is an unreasonable location.

SODA Days 0/1...

• Michael Lugo confirms that Analytic Combinatorics IS out !
• David E reports on two interesting theory-experimental papers from ALENEX
• David E mentions in passing a new result by Gabriel Nivasch on DS sequences, giving very tight upper and lower bounds for order 3 and higher.
  

That's it for now: come on, CS bloggers !

no SODA blogging :(

I'm not at SODA/ALENEX this year, so no blogging :(. If anyone is blogging/tweeting/facebooking from the conference, let me know and I'll post a link here. Michael Lugo from God Plays Dice will be at ANALCO, and will hopefully have more on the 'Impatiemment Attendu' :)

Flying While Brown, in 2009...

No beards, no scarfs, and DEFINITELY no discussion of safe places to sit:

Mr. Irfan turned to his wife, Sobia Ijaz, as they boarded AirTran Flight 175 at Reagan National Airport near Washington Thursday afternoon, and wondered aloud where the safest place to sit on the airplane would be — the front? The rear? Over the wing? 

But passengers sitting behind them evidently overheard the remark, saw Mr. Irfan’s beard and his wife’s head scarf, and grew concerned. Mr. Irfan and his wife, along with six members of their extended family, are Muslims, and were on their way to a religious conference in Orlando when they boarded the flight.

The worried passengers contacted flight attendants, who contacted Transportation Security Administration officials, and soon, Mr. Irfan and his wife were off the plane and being questioned in the jetway. The six remaining family members in the traveling party were taken off the plane as well, along with a family friend who happened to be on the same flight and who happens to be a lawyer for the Library of Congress. 

Next, the nine Muslim passengers — all but one are United States-born American citizens — were taken to a quarantine area in the passenger lounge where they were questioned by F.B.I. agents. Mr. Irfan’s three small nephews were denied access to food in the family’s carry-on luggage. 

Before long, Mr. Irfan told The Lede in an interview Friday morning, the F.B.I. concluded that the incident was obviously just a misunderstanding, and told AirTran officials that the family was cleared to travel. But he said AirTran still refused to rebook them, offering only to refund their tickets. The F.B.I. agents helped the family get on a later USAirways flight to Orlando, but those seats cost them twice as much.

Happy new year, same as the old year.