Sunday, January 30, 2011

SODA talks

I'm always a bit more interested in what exciting problems I'm introduced to at a conference than the proof techniques used in the solution (probably partially because the best talks often don't get into the details). So here's my report back from SODA, in the form of exciting problem descriptions.

Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures by Mark de Berg, Herman Haverkort, and Constantinos Tsirogiannis - This problem was described as the "farmer's problem," the problem of determining what fields upslope might contaminate yours by draining with the flow of the water.

Shortest Non-Crossing Walks in the Plane by Jeff Erickson and Amir Nayyeri - This problem is as the title describes. The authors also consider the version in which there are polygonal obstacles. It was a nice problem and made me wonder if a variation has been solved... For public transportation networks it might be interesting to consider short walks that cross as many times as possible (or some balance of short paths and many crossings). This could probably be a variation of a facility location problem. Obviously, the polygonal obstacles would also translate in the form of neighborhoods that hate public transit and block construction attempts (or, more generously, in the form of existing buildings). Anyone know if a problem of this sort has been considered?

And here's one where I really did just like the solution...
Fast, Precise and Dynamic Distance Queries by Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty - This paper relies on a series of other nice ones about dynamic spanners and hierarchies. The first in that immediate group is Deformable Spanners and Applications by Gao, Guilbas, and Nguyen, which set up a tree hierarchy based on local distances between points in which points in the same level of the hierarchy and within some distance of each other are considered neighbors for the purpose of creating a spanner. These authors make the nice observation that the distance between points in the hierarchy whose parents are neighbors are a good approximation for the distance between their descendants. The full algorithm and proof are, of course, much more involved. (For a better description, complete with beautiful pictures, see the slides linked from Lee-Ad's homepage.)

Finally, the award for the best previous work slide goes to Maarten Loffler for his talk on the paper Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent by Maarten Loffler and Wolfgang Mulzer. While I haven't been able to find the incredible slides online, the previous work flow chart can be seen on page 2 of the paper. If I drew cartoons, I'd be able to do a nice parody tribute to this. Instead, all I have is this phd comics strip about references.

Wednesday, January 26, 2011

SODA Business Meeting

I'll have technical stuff up later. For now, a report back from the longest business meeting ever (no, I have no data to support that assertion).

As ever, the highlight of the meeting was the decision on where SODA will be held in 2013. After choosing sides of the room, Miami won over New Orleans 67 to 62 (if I remember the numbers correctly). Despite a lot of yelling from the New Orleans side to clarify that Miami is not the same as Miami Beach, and grim reminders of the last time SODA was in Miami, no one switched sides. Still, it was a close vote. Perhaps the Miami decision will be overruled...

About 20 minutes after the meeting was scheduled to be over, the possibility of merging the associated workshops (ALENEX and ANALCO) with SODA as additional tracks (under the "ESA model") was brought up. There wasn't much discussion at the time, but the main worries seem to be a lowering in paper quality or the gradual dieing out of those submissions leading to a SODA as it is currently but without the associated workshops. Before the suggestion, I had been thinking a lot about why it was I had been so much more excited about ESA this past September than I was about SODA. I think the lack of experimental/practical emphasis had a lot to do with this. ESA, even the theoretical track, seemed a bit more focused on solving interesting problems. I hope SODA follows suit, whatever the method.

Thursday, January 6, 2011

Helping Teachers Helps Students

Apparently I'm doing a short (if somewhat spread out) series on education (previously here, here, and here). In this installment I'll discuss what I see as a replacement axiom to the teacher myth: teachers are the solution or helping teachers helps students.

First, a disclaimer: No one single group of people, no one single act can "fix" education. Students, teachers, administrators, parents, policy makers, and the general public are all responsible for the current state of education. (And the current state of education isn't all that bad, let's remember.) But certainly, if not agreeing that teachers are the most important, we can agree that they're important.

Many of the current educational efforts revolve around the idea of "holding teachers accountable." This often leads to efforts involving test scores and record keeping, only serving to increase the administrative burden on teachers. Teachers have a lot to do. Help them do it faster and they'll be able to spend more time actually teaching. They certainly can't become better teachers without that extra time for training, lesson plans, etc. Give teachers additional training, mentorship, etc. and they'll become better teachers. And that, in turn, will help students.

So, from a computer science point of view, what can we do to help teachers (and thus help students)? What can we automate? What tasks drain teachers' time while not giving them much in return? If you're a teacher, what tedious things do you spend your time doing? Some of these problems will likely be easy to solve, while some will require more creativity. We should tackle both.