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.

More experiments in algo-teaching

(ed. note: think of this as a 'theory'-chaser to take the bad taste of cricket-blogging out of your mouth)

Another experiment that I continued this time was a set of lectures on "fun topics". The idea is to convey some ideas about a fun topic in theoryCS without too much jargon, but with enough meat to indicate that there's something deeper going on beneath the fun stuff.

I run these lectures at the end of the semester (when everyone's worn out already :)), and throw them open to the general public: both times I did this, I got substantial attendance from people not in my class, and at least in one case, someone who attended the lecture last year actually decided to take my class this year.

Not all topics are amenable to such a treatment, but my hope is to build up a suite of such lectures: the nice thing is that they can then be reused for other venues: for example, I've given variants of these talks to freshmen and high school students, and will do an undergraduate colloquium in the math department next semester.

For all of these lectures, I've pilfered shamelessly from the original works, as well as great websites developed by the authors. This post can be viewed as a shout-out and a thank you.

1. Pancake flipping:
Brian Hayes wrote a great article on pancake flipping for the American Scientist. In it, he links it to the problem of genomic rearrangement, and in doing so, ends up with a beautiful tale of the interaction between theoretical problems and practical constraints, all told in context of a topic that everyone can relate to.

I made two-color pancakes in different sizes, and distributed them to the students at the start of class: I briefly described the problem, and let them go at it. It was quite entertaining, and put the more formal discussion later on in context.

2. Zero knowledge proofs
ZK proofs are great for this kind of setting: they are completely counter-intuitive, (and so have the 'bizarre' factor), and are easily explained using popular metaphors. I used Moni Naor's Sudoku demo page, as well as the version of the proof that involves slicing and dicing the puzzle. This was done with class participation (I was the prover, and there were multiple verifiers).

The second demo I ran was the Yao protocol for the Millionaire's problem (how do two millionaires determine which is richer, without either knowing the worth of the other). Again, I did this interactively with class volunteers and an RSA applet to speed things along. More details here.

3. Quantum Computing
No demos for this one, but I gave a crude high level view of what quantum computing is about (about one-step up from the "do everything in parallel" explanation). The main goal here was to convey the basic ideas of what a qubit is, what a quantum circuit looks like, and how the Bell inequalities show that quantum computing is much more bizarre than classical randomness. Here, Dave Bacon/Umesh Vazirani lecture notes proved indispensable, coupled with the Nielsen-Chuang book, and a recent blog post by Michael Nielsen.

4. Computational Origami
I haven't quite worked the kinks out of this one, but the basic idea is to demonstrate the principles behind computational origami (and where the 'computation' comes in) by looking at the question: What shapes can you make by folding, followed by a single cut.

There's a cool backstory to this: essentially the first example of such an algorithm was how Betsy Ross designed the 5 point star for the American Flag, and it lends itself to a nice demo in class.

Secondly, it's a classic example of resource-bounded computation: limiting yourself to one cut. Thus, it makes for a good illustration of how computation appears in all kinds of problems.

Thirdly, computational origami actually shows up in many real-world problems, most notable one involving folding mirrors for a telescope to be launched into space. If we're trying to convey a sense of computational thinking, this is a great example.

The actual problem itself was solved in this paper by Demaine, Demaine and Lubiw. Unfortunately, I have yet to find a way of explaining it that will make sense to non-expert geometers, and that's one weakness with this particular story: Erik's page has some nice examples to demo, but it's hard to convey the deeper algorithmics behind the problem.

Lessons learned:

• As always, know your audience. What works for a graduate class doesn't work for sophomores, and certainly doesn't work for eigth-graders :)
• Interactivity is key: if you allow people to participate, they're more involved, and will probably take away something positive
• Keep it light: resist the urge to get too mathematical. There are many beautiful topics in theoryCS that can be explained without jargon, and many others for which with some effort, jargon can be removed.
  
• A 'bizarro' factor helps: In general lectures that I've given, I find that presenting something completely counter to people's expectations catches their attention immediately, and leaves a lasting impression. ZK proofs have that property. Bell's inequality sort of does, but the impact would be more immediate if I could actually run a quantum experiment to demonstrate violation of Bell's inequality ;)
• Relate it to the real world: again, it's not enough to cite applications: one should try to show them as far as possible. In this regard, the Betsy Ross story is great, because it relates to something everyone (in this country) knows.
  

My goal is to add one or two such lectures to my arsenal each time I teach the class. For next time, I'm seriously considering running a live auction of some kind to demonstrate some concept in algorithmic game theory (suggestions on how best to do this are always welcome). Are there other such topics that might lend themselves to an entertaining, edifiying and educational experience ?

On run-chases

(ed. note: this is about cricket, not algorithms, or geometry, or computer science. you have been warned)

South Africa, the Netherlands of cricket, finally won a big game, beating Australia in Perth after a historic run-chase of 414. This of course follows India's famous run-chase, beating England in Chennai by chasing down 387. As Cricinfo points out, 9 of the top 25 run chases have come in the last 8 years (in a tally that dates back to 1902).

There's a detailed statistical analysis of these chases, but no speculation as to why they're becoming more frequent. The answer seems obvious to me though: the increasing scores in one-day cricket. A quick search of Statsguru indicates that of the 258 overall scores above 300 (first or second team) one 1-day games, 179 of these happened after 2000. Even to a casual observer, it's clear that the scores in 1-day games have gone up (and don't get me started on Powerplays).

Frankly, when all this fuss was being made about India's run chase, I couldn't quite understand why, because if you think of this as a one-day game, it's not too hard (and in fact India's coaches thought the same way!).

All in all, two exciting Test matches (and how often have we been able to say that)

Videotaping talks

Videolectures.net is a company that has taken on the job of videotaping and packaging conference talks. They're based out of Slovenia, and offer a good service: they take your talk and your slides, and sync up the talk video and slides so someone watching later on can follow along.

For examples, you can see my talk at ETVC, and here are the other talks. I first heard about this company when I was googling a paper and discovered that the ICML talk was online.

I originally thought that they only handle events in Europe, but they appear to have covered this year's KDD as well (although the coverage appears strangely limited).

Practical applications of 1-medians

From Optimal Home Location:

Have you been looking across many different neighborhoods for a place to buy or rent? Have you been contemplating whether to buy closer to your job, your spouse's job or your kids' school? Do not worry - this is not a simple geometric triangulation but a centuries old mathematical problem. Optimal Home Location tool is synthesizing math algorithms and Google Maps together in order to pinpoint optimal home location for any commute scenario. It is easy to use and fun to play with. All you need to do it [sic] enter all the addresses your family routinely visits throughout the day and then click on the map icons to define commute route for each member of your family. The tool automatically computes optimal home location that will minimize total combined commute for all members of your family

NSF bleg

This appears in the supplemental documents section of the upcoming CISE call:

In the Supplementary Documents Section, include a list of all PIs, Co-PIs, Senior Personnel, paid Consultants, Collaborators and Postdocs to be involved in the project. This list should be numbered and include (in this order) Full name, Organization(s), and Role in the project, with each item separated by a semi-colon. Each person listed should start a new numbered line.

Does anyone know what a "Collaborator" is ? is it merely your other-institution co-PI on a collaborative proposal ?

I had a number of responses to people from my programming project post: I thought I'd post the responses here, rather than in comment fields.

* On rolling your own: I'm intrigued by the many suggestions to use Sphere Online. I've heard of topcoder and Project Euler before, and decided not to use topcoder for ease of pedagogy (I wanted problems where the key algorithmic idea was "preidentified", so I could give a DP problem in the homework on dynamic programming). I was also not convinced that topcoder focused on the algorithmic aspects of the problem as opposed to raw speed: the fact that it was set up as a time limited competition by default was also a pain in the neck.

* On copying: this is an unsolvable problem IMO. Since I was choosing problems from the pre-canned list at the ACM server, I was at the mercy of the online solution providers. Judging by the results, my students are either very honest, or don't know how to find these sites :). I've spied on the related forums, and they tend to be somewhat militaristic about not letting people post code directly, although hints are always supplied. As an aside, for theory problems this is a royal pain: I've had to mask things in various ways to prevent a google search, and I have my own way of creating problems that I'm happy to reveal to someone who asks me directly :).

* on what to do for geometry: the problem is not the lack of a good code base. In fact it's the reverse problem. CGAL for example has many quality solutions already pre-coded, so I can't even ask students to use CGAL as a base framework. Given the limited time I have before semester starts, its debatable how much coding and test generation I can do on my own, so stay tuned...

I am less than smart :)

I posted my note on programming assignments, and then wondered why there were no comments. It turns out that I forgot to monitor my moderation list, and when I checked, there were tons of comments ! apologies to all the commenters: your comments are available now, and I'll start replying shortly.

programming assignments

Inspired in part by Michael Mitzenmacher's exhortation:

Here's my claim: theory does untold damage to itself every year by not having programming assignments in the introductory classes on algorithms and data structures.

I tried an experiment in my algorithms class this year. Using the ACM programming competition online judge as an evaluation tool, I assigned one programming assignment in each of the first three assignments in my class (later assignments went into approximations and randomization, which the site didn't really cater to). Coupled with this, I used the ACM Programming challenges book by Skiena and Revilla to guide my choice (they break the problems down nicely by dominant technique).

The way the system works is this: you're given a problem definition and an input/output specification. You write your code in one of three languages, using a specific compiler flag sequence, and then upload your code. The system runs your code through a battery of tests, and then reports whether you had

• compile-time errors
• failure to terminate in the prespecified time limit
• incorrect answers
• run-time errors
• all correct answers
  

What worked:

• Students actually liked the idea of programming assignments: I received numerous variations of the comment, "I didn't understand the algorithm, but once I coded it...". They were less enthused by the server, but more on that later.
• People started getting quite competitive: the site maintains stats on the best implementation thus far, and even after students satisfied the requirements of the assignment, by matching the desired time limit, they tried to optimize their code further.
• The questions are well-designed, and usually need algorithmic tricks rather than hacks. For example, one question is to compute the closest pair, and any optimized brute force algorithm will fail, but the standard deterministic divide and conquer will work fine.
  

What didn't:

• The server would occasionally flake, especially a few hours before assignment deadline time :)
• I/O specifications were often tricky: the problem specifications would leave out details about what one could assume about the input, so simple things like "don't assume that when a range [x,y] is given in the input, that x <=y" needed to be discovered.
• The error messages are cryptic to a fault. Compile time errors are linked to the point in the code where this happens, but for any other kind of error, you are merely told that an error occurred. This caused major frustration.
• With Java especially, getting a correct implementation within the time bound seemed harder than with C/C++. Since Java is often the first language students learn, this is annoying, especially since the whole point of such exercises is to abstract away as far as possible the particular idiosyncracies of a language.
• From a grading point of view, it's very painful to evaluate each person's submission. There's no easy way except to do it manually.
  

Overall, my experience was mixed-to-slightly-positive: I'll probably do this again, but I might also include examples where I design the test inputs and do local evaluation. For some problems (like with randomization) I might have to design the problem from scratch.

Now what I'd like is something similar for my computational geometry class :)

While in Paris...

My latest reason for being off the air has to do with the amazingly bad internet capabilities of Paris hotels. Yes, I'm in Paris, city of lovers, but certainly not of lovers of wifi. There are at least 30 networks visibile wherever you go, but they're all secure, so no mooching. The hotel-provided wifi is actually a generic service that costs 22 E/day for connectivity, with all kinds of bandwidth caps and a very slow connection. If I were to splurge for the "business" level, I get the luxury of paying 27 E/day, with unclear benefits (presumably I can now download my bootleg bittorrents (just kidding)).

Other things I've noticed since I last came to Paris: (which is not to say that they are new, just that I just noticed them):

• Every second store on the podunk street my hotel is on is a fancy clothing store. Clearly the world-wide economic collapse has not hit.
• Speaking of world-wide economic collapses, it really hurts to have a weak dollar. $7 espressos, sigh...
• ....but it's always a pleasure to walk into a cafe and order a 'cafe' and just know that something good will appear. This is in contrast to the unbounded depth circuit needed to specify a proper cup of coffee at Starbucks.
• Speaking of Starbucks, how on earth can they even survive in Paris ? I mean, you go to a Starbucks here, and you get the same experience as in the US, ending with a paper cup of coffee of questionable quality that you drink perched on a high bar stool. On the other hand, you go to a cafe, and they serve you with nice cups, and a little cookie, and let you sit there for hours nursing your coffee, and will even give you the WEP key for their secured WiFi. It's no contest !
• You can change the world while nursing your coffee. I was staying in the 14th Arrondissement (the Montparnasse area) and had to have a coffee at the Dome cafe, a place apparently frequented by Lenin and Trotsky before the Revolution. I have to say that at the time I went, the clientele looked like they were plotting a revolution... in 1907.... I'd link to a verification of this, but I can't make any sense out of the search results on google.fr
• Speaking of which, how does one tell google NOT to return results in french ? every time I edit the URL to go to google.com, it sends me back to google.fr. Suivant !!!

And why am I blogging from Paris, you might ask ? Well here's why. I'm an invited speaker, no less. Conference blogging was limited because there was no wifi at the conference site either. It's a long story involving military schools (and maybe even NASA). Details will appear shortly.

Coffee..

On the evolution of coffee drinking, by Malcolm Gladwell (he of The Tipping Point and Blink). I particularly like this line about Trotsky:

Give a man enough coffee and he's capable of anything.

Items...

I've noticed an inverse correlation between blogging frequency and "actual work", so boy must I have been working hard !!

Two items of note, as my blog and I pass in the night:

• Michael Nielsen links to a great way of advertising a speaker: use Wordle on their work (delicious feeds/research papers)
  
• ICML 2009 is going to a reviewing model where you can specify which area chairs you want your papers directed to (area chairs and interest areas will be listed). John Langford, one of the area chairs, goes further with what is essentially a personalized reviewer manifesto. An excellent idea ! He lays out his principles, and authors are fore-warned.