kd-PhD

An Update from the Void

2011-11-29T22:38:00.002-05:00

I've been a bit quiet lately, I know. I find it's hard to talk about anything when I'm not allowed to talk about work, and I've been working hard on an unreleased project. It's been wonderfully exciting and interestingly hard, and we launched today so I can finally say (a little) about what I've been spending all my time doing.

I'm part of the indoor maps / location team. Some of you may remember that I'm somewhat obsessed with maps. Now I get to work with lots of other people who are also obsessed with maps. (Did you know that for a long time California was thought to be an island?) Surprisingly to me, there's only a small amount of Computational Geometry being used in all of this, so I've been getting a crash course in Machine Learning, which has been enjoyably educational. I am, of course, planning to inject geometry wherever I can... perhaps eventually I'll be able to give an update on that as well. Until then, I'll have to make do with telling you to download Maps 6.0 and give it a try.

Online Courses

2011-03-19T21:06:00.000-04:00

One of the questionable outcomes of the teacher myth has been the increase in online courses at the K-12 and college levels. (Here I mean courses taught entirely online, in which students and teacher never meet face to face and much content is learned by the students on their own by reading through online content.) On the one hand, putting information online is great (if it's open content) - students all over the world who don't have access to formal education can learn from it. Teachers can use it in their own classrooms, thus avoiding reinventing the wheel more than necessary and saving them time. But I worry that it walks a dangerous line inspired by the teacher myth: teachers are unnecessary. What about role models, emotional support, and the ability to ask questions?

Anything perpetuating the idea that teachers are unnecessary also potentially supports other problematic corollaries of the teacher myth, leading to the replacement of tenured unionized teachers with lower paid adjuncts (both at the secondary and college levels). All of this contributes to the de-professionalization of the field. So while we may be pro-online content and generally pro-technology, we should carefully consider the real consequences of being pro-online courses.

SoCG Accepted Motion/Sensing Papers

2011-03-06T20:04:00.006-05:00

Yes, this is somewhat delayed. Better late than never?

Here's the list of exciting-looking motion/sensing papers culled from the SoCG 2011 accepted papers list. Also known as my to-read list.

Mark de Berg, Marcel Roeloffzen and Bettina Speckmann. Kinetic Convex Hulls and Delaunay Triangulations in the Black-Box Model
Umut Acar, Benoît Hudson and Duru Türkoglu. Kinetic Mesh Refinement in 2D
Rishi Gupta, Piotr Indyk, Eric Price and Yaron Rachlin. Compressive sensing with local geometric features

Sadly, none of these seem to have a pdf preprint up yet, providing me with yet another excuse for procrastination...

A Full Day of Grading

2011-02-09T22:25:00.001-05:00

Teachers, TAs, and professors love to complain about the amount of grading they have. But how much is that, exactly? I've seen studies that say assessments and assessment-related activities (I imagine this includes creation, proctoring, and grading) take up 1/3 - 1/2 of a teacher's time. I certainly believe it. But I thought it might be interesting/useful/fun procrastination to consider a rough estimate of how many hours per week it might be reasonable to expect a teacher (in this case, imagine a high school teacher) to spend just grading. And I found what I came up with to be rather amazing (despite all the time I've personally spent grading).

Here are my basic low-end assumptions:

A teacher has about 100 students (imagine 4 classes of 25 students each). These days, many teachers teach 5 classes of 30 each. Some pampered private school teachers (like I was) teach 4 classes of 15 students each. Still, 100 is a reasonable estimate and a nice round number.
Each student hands in one page to be graded each day. This will likely be a single sheet of homework. This excludes any tests or quizes, which are generally longer than a sheet, so this is definitely a low-end estimate.
Each page takes the teacher 1 minute to grade. Again, this sounds like a short time to me if you're actually grading the work. And if you also consider the time it takes to determine the full-page grade and enter it into the computer system...

These estimates lead to a need to grade 500 pages per week, which I'm estimating could take 500 minutes. That's 8.33 hours, or a full work day. Yes, a teacher could easily spend a full work day each week just grading. I find that astonishing.

SODA: Instance Optimality

2011-02-01T00:04:00.000-05:00

The highlight of SODA for me was the plenary talk Computational Geometry for Non-Geometers by Timothy Chan, especially the part in which he discussed instance optimality. The basic idea is to consider algorithm analyses that take all inputs into account and operate optimally over all inputs in comparison to an algorithm designed specifically for that input (but not for that input's order). I believe this was first considered in a geometric setting (Instance-Optimal Geometric Algorithms), so you could imagine that the input is a set of points and the algorithm you're competing against doesn't know in advance in what order the points will be given to you. This wonderfully fixes the problem with worst-case analyses in which an algorithm might perform poorly on most input instances but there is some hard instance for which the performance is reasonable. Instead, under an instance-optimal analysis, the algorithm is expected to perform well on all input instances.

In the study of data structures for moving objects, a similar idea known as motion sensitivity was previously introduced under a motion-specific setting. Motion sensitivity generally describes algorithms that perform well under orderly motion and have performance that degrades as the point motion becomes more random. In my own work, I consider entropy-based analyses in order to capture this concept. In fact, the instance-optimal analysis Timothy described also resulted in an entropy-like inequality, so perhaps this relationship is inevitable/necessary for these analyses.

It's an exciting new area that I'm hoping to see a lot more of. It was certainly an excellent talk.

SODA talks

2011-01-30T22:37:00.000-05:00

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.

SODA Business Meeting

2011-01-26T20:40:00.000-05:00

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.

Helping Teachers Helps Students

2011-01-06T19:47:00.000-05:00

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.

Teacher Tenure

2010-11-01T18:58:00.000-04:00

A commenter on my previous post says:

Since the career path of a teacher is distinct from most others, the onus seems to be on those who do not want reform: what makes teaching different from so many other jobs that necessitates such a drastically different incentive structure? Put another way, do you think that software engineers at Google should be granted tenure, in exchange for significantly lower pay, and significantly lower accountability?

Obviously, teacher tenure is a gigantic issue, but I'll try to address some of the points here.

First, it bears mentioning that in fact the career of a "teacher" (here, I'll use the term to refer to a K-12 teacher, which I believe is the main meaning of the term in this discussion) actually follows a similar career path to that of a "professor" (college/university teacher). In that context, it makes sense that teachers would have the possibility of tenure just as professors do. (Note that tenure for professors also seems to serve as a replacement for higher pay.)

But perhaps you are against tenure in all contexts? What, you ask, makes teaching different?

Schools are not a business. The goal of a school is not to make money, it is to educate. This means that teachers' jobs are fundamentally different than industry jobs. While this doesn't obviously directly impact the tenure question, I think it's important to keep in mind that what works for industry doesn't necessarily work for schools since they have fundamentally different goals.
Schools are integral to communities. Students are more successful when they are part of a sustained community, when they have consistent adult mentors. They're more likely to show up for school and have a positive relationship to it. But "mentoring relationships of short duration may do more harm than good." So schools are more effective when teachers stay in the school for the long term. Tenure is an incentive for teachers not to move schools frequently. There are other ways to incentivize this, for example Google provides many well-known perks to convince us not to leave - great food, a shuttle service for commuters, etc., all free to employees. But schools are unlikely to do that.
Teachers need intellectual freedom. Teachers are, unfortunately, under the whim of politically run school boards. Without teacher tenure Texas might have lost all science teachers willing to teach about evolution. Just to name one example.
Evaluation of teachers is not a solved problem. Because of the vast number of variables that interact to create student achievement, evaluating teachers is not a solved problem. It is, for example, drastically harder than evaluating whether someone in sales is performing well.
Teachers aren't paid well. This last point is large enough to eclipse all the others, in my opinion. Enough so that I'd consider being for the abolition of teacher tenure if this point were fixed (and a reasonable evaluation structure was put into place). Teachers have high stress high responsibility jobs. They're held accountable for all mistakes in the classroom and those mistakes have real consequences. They should be paid like stock traders, if stock traders weren't allowed coffee breaks. For more on pay and on evaluation, see my previous post on Teachers Have It Easy.

For more examples, citations, and clarity (as well as a bit more attitude) see an NYC teacher's take on the issue.

The Teacher Myth

2010-10-26T18:41:00.000-04:00

A lot of high profile people have been saying some things about teachers in a lot of high profile venues that I think are based on a main faulty assumption with some therefore faulty corollaries. (If, for some bizarre reason you don't care about K-12 education and think that this has nothing to do with you, I'll get to that in a future post on the trend toward online teaching. For now, humor me.) I'll call this set of faulty beliefs "The Teacher Myth" and attack them point by point below.

The Teacher Myth in Education Reform:
Teachers are the problem. - In an effort to believe the best in everyone, I believe that this negative statement actually comes from a positive belief: "Teachers are the solution." I do believe that. (Of course, they're not the only piece of the solution, it's a multi-part problem that many people/communities need to work together to solve.) Teachers are the main point-of-contact between students and schools. They're the public relations department and the product of a school. And a few remarkable teachers have the amazing ability to single-handedly save a bad situation. That may sound like I'm saying that teachers are the problem, but having the ability to solve a problem is not the same thing as having caused it.

Unions are the problem. Teaching is a field dominated by women, so it has traditionally been paid as if it is a second income job. In other words, less. In fact, if I'm remembering the stat correctly, teachers make less money than any other field with the same education level. (For more accurate stats and general explanation about this point see Teachers Have It Easy.) Teachers also work longer hours under harsher, more critical conditions than most other professional fields. Even finding time to use the bathroom can be challenging in a teacher's non-stop day. This is precisely the type of job that needs a strong union. Unless you don't believe in unions? That's a different issue.
Tenure is the problem. There's a bizarre idea that many people hold (and that many teachers perpetuate) that teaching is a calling - as if it were the priesthood. Teaching is a job. It's a job that requires a high level of education, doesn't pay very well, and has long stressful work hours. It does have one important perk - job stability. That perk "makes up" for some of the lack of pay. People operating under the teacher myth believe that we have a shortage of good, qualified teachers. Removing one of the main job benefits of teaching is not a good way to get more.
Anyone can teach. Teach for America and other similar organizations have done a great job perpetuating this sub-myth. It's great that these organizations are convincing more people to go into teaching in the short term, but their goals aren't to create professional teachers - they expect recent college grads to teach for two years and maybe stick around for a year or two after that. It's something to do before going back to law school. But teaching is a profession and teachers, yes, need to learn how to be teachers. It takes time, skill, training, and effort. Just like all professional jobs.
Paying good teachers more is a solution. Paying teachers more is great. Teachers should be paid more! But this also implies that bad teachers should be paid less. Who are "bad teachers?" Have they been branded as such permanently? I believe that no-one goes into teaching, or any profession for that matter, trying to be bad at their job. The "bad teachers" want to do a good job! Why not focus on training them to do that? I just started as a Software Engineer at Google. I got 2 weeks of intensive training at the beginning. I'm still in the middle of 10 weeks of at-my-own-pace online lessons. And I have an assigned mentor who sits near me. This is all despite the fact that I have a Ph.D. in Computer Science. Don't teachers, starting jobs after their own academic training programs, deserve at least as much before they're permanently labelled as failing?
Bad teachers can be easily identified. Or, restated, bad teachers are like porn, you know them when you see them. One commonly encouraged way to identify "bad teachers" is to use standardized test scores - the bad teachers will be the ones with the low student test scores. But what are the students like in their classrooms? What are the students' home lives like? How long has the teacher been teaching (they do get time to learn themselves, right?)? And, the biggie, who says that standardized test scores actually measure anything relevant? If they don't, then do we trust principals to evaluate teachers? Will superintendents step in to evaluate the principals' evaluations, etc.? To use the "you know it when you see it" metric, someone besides the teacher will need to take the time to show up in the classroom regularly and give thoughtful, constructive feedback. This is all too rare. And obviously, bad teachers aren't like porn. It's much more complicated.

So please, before you jump on the bandwagon of some reform idea (or movie) or another, stop to think about it's underlying ideas. Is the teacher myth one of its axioms?

Superman's Statistics

2010-10-22T18:04:00.001-04:00

Wired Magazine has an article in their September issue on "7 Essential Skills You Didn't Learn in College." One of their proposed new courses is Statistical Literacy. Indeed, this is one of the areas in which many American students leave school unprepared. The new movie Waiting for Superman capitalizes on this fact to discuss, ironically, school reform. Here are a two statistics from the movie* that school should have taught us to question:

On average, more money is spent per-student now than in 1970. Did they really just cite a mean statistic when talking about money in the US? The top 1% of US earners throw everything off and are also likely to live in the same neighborhoods, putting money into the same schools. What are the median statistics? Also, how has the student body being served changed over that time? For example, are there more English Language Learners (ELL) students? Are more students being diagnosed with ADHD and getting the extra services they need? There are many such trends that might increase even the median amount without actually increasing the "average" money spent per "average" student. Plus, why is spending more money on our public schools a bad thing? What's the average cost per private school student?
Average US test scores have not increased since 1970. Again, I say average? Student body composition? Composition of students taking the test? Also, what test?

In addition, the schools that they do highlight as doing well on standardized tests (is that the appropriate goal?) actually spend much more than the current national average per student to achieve that, so in addition to the statistics being murky, they're not actually making the movie's point.

In a later post, I'll hopefully get to the many other issues of this movie. For now, let me just remind you that, as Mark Zuckerberg would agree, you shouldn't believe everything you see on the big screen.

* Obviously, I don't remember the statistics or wording exactly from the movie. So, disclaimer, this represents the gist as I remember it. Of course, since their statistics weren't explicitly derived to begin with, these might just be the same numbers under a slightly different model.

Water in a Cube

2010-10-05T21:19:00.001-04:00

I don't often come across visualization problems that I can't see the answer to in a few seconds. (I mention this since I too frequently come across people who assume that because I'm female I must be bad at this. Remember, I do geometry.) So I was very excited when I was recently given the following tricky visualization problem:

Suppose you are given a cube. Stand it on one vertex so that the diagonally opposite vertex (the one with which it shares no faces) and your vertex create a line perpendicular to the ground. Now fill the cube halfway with water. Looking straight down, what shape is the surface of the water?

Published with Blogger-droid v1.6.2

ESA 2010

2010-09-15T21:22:00.008-04:00

I went to ESA in Liverpool two weeks ago (yes, this is late). It was an excellent conference all around (despite it's somewhat impossible to get to from the US location). Here is my biased take on the highlights:

Median Trajectories by K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, R. Silveira, C. Wenk and L. Wiratma - An exciting paper defining and creating algorithms for a median trajectory. The idea of the problem is: Suppose that you know trajectories along which points were moving and want to define some "median" path, for example signifying a good walking route. What is an appropriate definition of such a common trajectory and how can it be calculated? This is a nice, and to my mind obviously important, problem statement. Worth a read of the paper. (Plus, it should be noted that this paper wins the award for shortest title and, as Mark de Berg pointed out during the business meeting, all papers with 2 word titles were accepted.)
Folks from Google Zurich (with paper Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns by H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V. Raychev and F. Viger) talked about the ways in which they solved the problem of routing in public transportation networks and how that's different than routing in street networks. One example they gave that was emblematic of this type of problem was suppose that all buses leaving from a given location have stopped for the evening, but intercity planes or trains have not, then the route needs to return a wait time, not a detour out of the country and back in to approach the location in a very circuitous and more expensive way.
Paolo Ferragina was one of the invited speakers. I'm particularly interested in his work, so I was excited about his talk already, but I wasn't sure if he was a good speaker or not. He is. He structured his talk as a history of data storage issues and trends and even though I had read many of the books/papers previously, everything made much more sense as he explained it. Unfortunately, I had to leave the talk a few minutes early (due to the impossible to get to nature of Liverpool and my correspondingly annoying flight plans) and so I missed his descriptions of the future of practical storage/retrieval algorithms and analysis. According to the title, they have something to do with joules, but I'll have to read the corresponding paper for the result of this cliffhanger. If it's anything like the talk, I recommend you do the same.

Also, the food at the banquet was really good. Credit where credit is due.

Ph.D.!

2010-08-24T11:50:00.003-04:00

I can now legitimately have a blog titled kd-PhD. Last month, I defended my dissertation (and passed)! It was terrifying, but I also always enjoy presenting my work to an engaged audience, and the (perhaps somewhat captive) audience was excellent. My liberal arts background ended up seeing me through to the end - in addition to the more expected scientific questions, there was a question about Foucault!

If you would like to be one of the proud few who have read my thesis, it can be found on on my website.

Since then, I've been packing, moving, on vacation, and am now in San Francisco! I start at Google next week.

Theorists Getting Jobs

2010-07-12T23:26:00.005-04:00

I've been trying to think of something intelligent and biting to say about the appalling comments in response to Bill's post about what jobs theorists ended up with. I haven't come up with anything other than the need to point out that the shock and supposed horror about the lack of qualifications of someone who was privileged enough to get an excellent job this year was only present about a female candidate. And she had a two-body problem - oh the horror that a woman with a two-body problem would not have to sacrifice her career and might even be an excellent job candidate on her own! Whatever will happen next?!

Enough about that. No need to continue that lovely conversation here.

Instead, I'd like to point out that (among the bemoaning of the lack of jobs, which is totally true) there was very little discussion about those of us "stealth theorists" who are taking our theory and going practical. Yes, you can have your theory and eat too.

Top Three Pieces of Advice

2010-07-01T13:48:00.003-04:00

I've gone to a bunch of women in computer science focused events over the past few years. Of the many pieces of advice shared, these are the three that have really stuck in my head. They're paraphrased, but hopefully correctly attributed.

While men can get away with not having a Ph.D. and still be respected in the field (see Gates, Bill), women can't yet. Get one. Then do whatever you want. - Mary Lou Jepsen at Grace Hopper
The reviewer of your paper is always right. If they completely misunderstood the paper, you now know you need to rewrite it. - CRA-W Grad Cohort "How to Write a Paper" session
Spend money to make your life easier - Women in Theory "Work/Life Balance" panel. Also heard at a Grace Hopper panel in the form: If your mother-in-law is coming to visit the same weekend as a paper deadline, pay someone to clean your house.

Have other advice? Do share.

You Must Be Really Smart

2010-06-29T15:37:00.000-04:00

(One of the other participants at the Women in Theory workshop brought up the following point during the question-and-answer session with Shirley Tilghman. It struck home.)

Before going to grad school, I taught middle school math for a year. Whenever I met someone new and they asked me what I did, I almost universally got the response "I hated middle school and I hate math." Encouraging, I know. I developed a standard response explaining how teaching middle school is not the same as actually being a middle school student again, and how middle schoolers are often nicer to their teachers (remember, we're not their parents) than they are to each other. I never did figure out how to address the second half of the response.

As a computer science Ph.D. student I get a very different response - "You must be really smart." It's been 5 years, but I still haven't figured out how to respond.

It never occurred to me, until pointed out last week, that male computer science Ph.D. students don't get this response. (You don't, right? I still find this shockingly hard to believe.) What's actually being said to me is, more honestly:

You do computer science? But that's a field that men do, and you're not a man so that doesn't make any sense! Men are just naturally better at computer science than women. And you're getting a Ph.D.? But that's something men do, and you're not a man! I guess the only explanation is that you must be really smart.

Women in Theory

2010-06-27T16:35:00.001-04:00

The workshop for women in theoretical computer science was first held in the summer of 2008 and was held for the second time last week. That makes it this blog's two year anniversary.

One of the things that makes Women in Theory different from most of the other conferences for women in computer science is its emphasis on technical talks. (This is one of the differences that I heard mentioned at the workshop as critical to many of the participants wanting to come.) In fact, all but three of the talks were 1 1/2 hour technical survey talks, designed to give enough background to understand some of the research in a particular area. They were uniformly excellent. (In fact, if you're interested in doing research in one of the areas surveyed, I highly recommend you watch the video of the talk for that area, which should at some point appear on the workshop webpage.) Were the talks excellent because women are naturally good at giving talks? It seems more likely to me that these women had two important things going for them - some serious skill in their field and the desire to give a good talk.

Even though the workshop was predominantly filled with technical talks, I'm going to misrepresent it here by mostly talking about the "women talks." The first was by Jesse Ellison from Newsweek about the state of women in the workplace. It was based mostly on this article and you should also look out for the video of that appearing on the workshop website.

As in the last workshop, there was a work/life balance panel including all the technical talk givers who were still there. I've now been to many such panels, and as usual there were these two unanswerable questions from the audience, "When is the best time for me to get pregnant?" and "How do I get self-esteem?" The answer to both is essentially "Whenever you're ready." But there was some excellent advice offered: be willing to spend money. That was mostly in response to how to deal with working while having a small child (good child care is a great thing). I would extend it generally to all of grad school (and likely beyond, I'll let you know once I get there). I spend most of my time working in a local cafe with my coffee and lunch. Yes, it costs more than working at home would, but I'm more productive at the cafe. For me, writing a paper intro is worth the cost of lunch.

The president of Princeton, Shirley Tilghman, also spoke. She gave a concise and focused talk describing the four reasons that we should all care about the number of women in the sciences:

Leaving out half of the world's work force isn't the best strategy for good scientific progress.
Science and technology will start to look left behind and out-of-date (as more and more women enter the workforce worldwide) and no-one will want to join our fields.
By including women, you increase the number and type of problems considered. What intrigues women is different (though we don't do the science differently). (Tilghman acknowledged that this point is controversial and gave the example of Liz Blackburn, Nobel Prize winner, who discovered the structure at the ends of chromosomes by working with an organism, pond scum, that no one else was working with. Despite skepticism, Blackburn believed her approach was correct and continued to work on it independently.)
It's unfair/ unethical to create exciting/interesting fields and then structure them so that they have barriers to women and underrepresented minorities. Universities, especially, shouldn't accept cultural norms that work against women. (For Tilghman's response to questions about what specific structures she's referring to, see the video of the talk.)

I highly recommend going to the next workshop (hopefully in 2012), if you can. Much thanks to the organizers, Tal Rabin, Boaz Barak, and Moses Charikar!

SoCG, Day 3 and MASSIVE

2010-06-19T22:58:00.003-04:00

I suppose that before I get too wrapped up in the next conference, I should say a bit about the previous two.

The last day of SoCG featured the second invited talk. Claudio Silva spoke about verification of visualization software. For example, suppose a doctor does a CAT scan and then looks at the resulting images to determine if/how/where surgery should be performed. It'd be good if that visualization was accurate. And in fact, sometimes it's not. (Scary, I know.) He's been working on (and succeeding at) developing algorithms to verify that the visualization is accurate. Nice problem.

The second workshop on massive data algorithmics (MASSIVE) was held the day after SoCG. It was small and excellent. I gave a talk on range searching over compressed kinetic data that, while not in the standard I/O-efficient trend of much of the conference, does begin the path of working on how to deal with massive data generated by moving objects.

The highlight of MASSIVE for me, other than the good food and company, were the two talks on the MapReduce algorithmic framework for parallel/distributed computing. I've never been particularly interested in parallel algorithms since they always seemed annoyingly messy to me, and the frameworks somehow weren't compelling. This framework, however, seems elegant. (And yes, it's patented and used by Google, where I'll be working in a few months.) I won't try to explain it here, but even if you're skeptical about designing parallel algorithms, it's worth looking into.

About 30 seconds after the last talk of MASSIVE had ended, the electricity went out. Nice timing, conference organizers. Congrats and thanks to Suresh and the other folks at U. Utah and to MADALGO.

SoCG, Day 2

2010-06-16T01:18:00.005-04:00

The highlight of today was the weather and the trip up the mountain (by tram) to this incredible view at the top. Yes, the sky was really that blue, and yes, that's snow we were standing on. You can see Salt Lake City in the valley in the distance.

Otherwise, the day started with another good talk by Chazelle introducing the problem of understanding the convergence of collective motion. He gave a beautiful example about fireflies in Thailand and Malaysia that flash simultaneously.

I won't go into detail, but two other papers I found interesting/ exciting are:

Dynamic can sometimes get close to kinetic...

SoCG, Day 1

2010-06-14T17:24:00.011-04:00

I'm here in beautiful, cold, Salt Lake City (or really, in Snowbird, a ski resort in the mountains above the city) for the Symposium on Computational Geometry. So far, it looks like it's going to be a great conference.

I don't know if the first session was purposefully packed with excellent talks, or maybe it just happened to be a session I was interested in, but not only were the results interesting, the talks were good too. Some highlights:

Optimal Partitions Trees and Tight Lower Bounds for Halfspace Range Searching:

Timothy Chan presented a new data structure for range searching with essentially the same bounds as a previous structure by Matousek (aside from preprocessing costs), but which has the important properties of being simpler (implementations possible!) and being based on a multilevel partition tree approach, which is useful for many applications. In fact, this upper bound was shown to be matched later in the session by a lower bound requiring this partition tree approach. David Mount presented that joint paper with Sunil Arya and Jian Xia. (Another connection between the two talks was the levity provided by Dave's attempt to open a Mountain Dew bottle in the middle of Chan's talk - a bottle I suspect was purchased at the bottom of the mountain and then driven up 2000 feet, thus providing for an explosive change in pressure...)

Consistent Digital Line Segments:

This talk provided, for me, an introduction to a really beautiful problem I had never thought in depth about before. The problem is essentially about defining methods for drawing digital lines (lines that are drawn with pixel paths) that are consistent with underlying geometric axioms - ideally axioms that define the important pieces of the intuition about lines that we have taken from Euclidean geometry, for example, two lines should intersect in only one place. It's a nice problem (and solution) that seems to go to the literal heart of computational geometry.

The Geometry of Flocking:

Chazelle presented a continuation of his work on natural algorithms, with a focus on bird flocking. I've written about this line of work a bit already, and don't have much more to say, but I'm looking forward to hearing another talk by him later in the conference.

Discrete Geometric Structures for Architecture:

The invited talk today was by Helmut Pottmann of the Geometric Modeling and Industrial Geometry group at Vienna University of Technology. I must admit, I was skeptical of a talk by a non-geometer, but it was excellent. It was about modern "natural" architecture (like the picture above that I stole from the group page), a style in which architects eschew the traditional lines and right angles of buildings in favor of a more curved appearance. He spoke about types of meshes that could work with these design concepts. I can't do the talk justice here, and I do hope that he puts the slides online.

Lunch today featured the student meet-up that was discussed after the 2008 SoCG, forgotten for awhile, and revived by Suresh in an email to me last week. In other words, it took very little organizational effort - Suresh made an announcement this morning that any interested students should meet outside the conference room at lunch time. Then we all went to a deli, got sandwiches, and took them to a room to eat. About 8-10 students showed up (though we lost some to the need to change rooms to sit down to eat) and it was nice to sit and chat. Thanks folks for showing up and thanks Suresh for making this happen! I hope it continues at future SoCGs - it's certainly worth the effort.

Finally, the business meeting was relatively uncontroversial. SoCG 2012 will be at UNC Chapel Hill (the only bid). If I remember correctly, attendance this year is somewhat down at 105 (compared to about 135 last year and 141 the year before in Maryland). Student attendance is correspondingly down to 28 from about 45. (So getting 8-10 students at the informal lunch is actually pretty good!) All numbers may be somewhat made up since I didn't write anything down. There was some encouragement from the current PC chair to continue the not-actually-a-rebuttal process next year, but no guarantees. Next year in Paris!

Range Searching Over Compressed Kinetic Data

2010-06-08T09:57:00.003-04:00

The ESA 2010 accepted papers are up. My advisor, David Mount, and I have a paper accepted there - "Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data." There is a (not yet revised and camera ready) version on my website. I'll also be presenting the paper at MASSIVE, a workshop held in conjunction with SoCG, next week.

The motivation of our paper (and generally, of much of my thesis) is to provide an observation-based framework for kinetic data. An earlier post talks more about why we'd want to do that - essentially the goal is to model scientifically collected data from moving objects. In the previous paper, we presented the framework and an accompanying compression scheme. In this paper, we're solving the problem that occurs when you realize that you've compressed all your data but still want to be able to query it (ideally, without decompressing it). We consider spatio-temporal queries, essentially the intersection of a temporal range and a spatial one - answering questions like "how many cars were observed on my street yesterday during rush hour?"

The abstract:

As sensor networks increase in size and number, efficient techniques are required to process the very large data sets that they generate. Frequently, sensor networks monitor objects in motion within their vicinity; the data associated with the movement of these objects is known as kinetic data. In an earlier paper we introduced an algorithm which, given a set of sensor observations, losslessly compresses this data to a size that is within a constant factor of the asymptotically optimal joint entropy bound. In this paper we present an e cient algorithm for answering spatio-temporal range queries. Our algorithm operates on a compressed representation of the data, without the need to decompress it. We analyze the efficiency of our algorithm in terms of a natural measure of information content, the joint entropy of the sensor outputs. We show that with space roughly equal to entropy, queries can be answered in time that is roughly logarithmic in entropy. In addition, we show experimentally that on real-world data our range searching structures use less space and have faster query times than the naive versions. These results represent the first solutions to range searching problems over compressed kinetic sensor data.

Women: Objects Unable to Survive Without Telephones

2010-06-03T12:59:00.004-04:00

Today, in the name of science, six men got into a locked chamber where they will stay for the next 520 days in order to simulate a trip to Mars. "Why all men?" I wondered, thinking that perhaps there were deep psychological reasons that it was better to have an all male "crew." According to one article, it's actually that women can't handle not talking on a telephone for 520 days:

"It is harder for a woman to be taken out of life and put in isolation," said Mars500 project director Boris Morukov.

"The most important thing here is motivation, and limitations would upset women. You're not allowed to talk on a telephone," he added.

And, of course, "women" not being there now becomes something for the rest of the crew to miss. You know, in the way women miss using telephones, men miss being able to use women.

The crewmembers said they would miss women terribly during the simulated trip but that the sacrifice was worth it.

In fact, the quote by the crew member right after this line makes it clear that it's not "women" he will miss, but rather his family, including a particular woman - his wife - and probably also including some men as well.

"It will be hard but I just try to recall all the great travelers who found the New World and who were also without their families," Sitev said.

So in fact it's not that the scientists will miss "women," but that they'll miss everyone other than the 5 guys they're stuck in a metal tube with. As would anyone. In fact, that's the point of the experiment to begin with.

Packing Rectangles

2010-05-25T14:27:00.003-04:00

Suppose that you have an n by n square made up of unit squares (we can think of this as a chessboard) on which you want to place R non-overlapping rectangles also made up of unit squares. How many ways can this be done? The board need not be covered.

There are many known variations of this problem, but the one that's most closely related that I can find solves this problem for R=1, in which case the answer is (n(n+1)/2)^2. I imagine that the problem has also been considered for general R, but can't seem to find it. Tips or ideas?

HollaBack!

2010-05-19T15:15:00.002-04:00

For those of you unfamiliar with the site, HollaBack NYC is a blog where people can submit (anonymously if they prefer) incidents of street harassment, often complete with a picture of the perp. The idea behind it is, of course, that no-one should have to accept street harassment as a given, and that it's good to have a way to, for your own sake and others', have a record of the harassment. It's somewhat of an institution, and has been around since 2005. Since then, it's grown into a larger movement and there are similar websites for other cities.

Now, they're planning to make it into an iPhone app (and are seeking funding). My understanding is that the app would partially serve the same purpose as the website, but in an easier, more immediate way - get harassed, use the app. It would also allow them to expand worldwide. But, more excitingly to me, it'll also serve as a means to collect data. How large is the problem? What neighborhoods/states/countries are the worst? What kinds of harassment are most common? How does time of day/ year change this? And could we see maps of that please?

If you're unfamiliar with the issue, or just with HollaBack itself, I definitely recommend taking a look at the site, or at least the FAQs.

Google

2010-05-12T11:26:00.004-04:00

It's official. I have a job for next year, and it's at Google. As seems to be their practice, I don't really know what I'll be doing, and won't until I get there, other than that I'll be a "Software Engineer." I suppose that's so I can't tell all of you! I'm hoping it's something nicely geometric, and maybe even something that relates to my research on kinetic sensor data. They certainly have a lot of changing data.

But, despite my theory bent, or perhaps because of doing mostly theory for the past few years, I'm excited to make something that people will actually use. The liberal arts student in me likes to learn about and do lots of different things, and I think I'll get to do that there. I was also really impressed with my interviewers - it seemed obvious that I'd learn a lot by working with people like them. Certainly, I won't be bored, and that's something I've been realizing lately is incredibly important to me.

I know many people may consider that this means I'm leaving research. Instead, I'd say that I'm going to be working on practical research. It will probably mean less papers, but more working systems. Research vs. Industry. It's a false dichotomy, or perhaps I just think it should be.

Googleless

2010-04-15T15:36:00.004-04:00

I seem to have some sort of strange web virus. Yesterday, it left me confused for awhile as I tried to go to Google and found myself instead at the Stanford homepage (which I had never previously visited). Thinking that my search for some computer science related term had somehow landed me there, I tried other ways of getting to Google. No such luck. All paths led to Stanford. Try going to update this blog? Stanford (with a "this page does not exist" error). Google news? Stanford. Gmail? Stanford. Another web browser entirely? Stanford. It seems that the virus somehow does a string replace for "google.com" with "stanford.edu." Great. Without Google, I even had trouble searching to find anything out about the virus. Resorting to the tried-and-true method of computer geeks everywhere, I restarted my computer. It's almost back to normal (note the Stanford mini-icon):

Of course, all searches containing both Google and Stanford just lead to information about Sergey Brin and Larry Page.

Thinking myself free, except for the mini-icon haunting, I celebrated with many Google searches. Now all attempts to get to facebook take me to Windows Live...

Powerless

2010-04-14T16:07:00.003-04:00

A power outage at my home last night took me back to my days living in Ghana: It was complete. It went on for awhile (6 hours? I was asleep by the time it ended...). It was unexpected (by me) - yet apparently planned (by the power company). As my reminders from Monday attest, this is a week with many deadlines, which makes me wonder:

If you are someone who experiences such outages frequently (perhaps you live in Ghana, or just in SE DC), how do you deal with this in relation to work? Do you submit "early and often?"
Do PCs care if this is why your submission is late? Would you contact them and ask for a personal extension if this were the reason? Should they care? Either way, is this another advantage that those "in the know" have over everyone else? (One "in the know" advantage seems to have been done away with at ESA this year.)
Is this yet another subtle way that the conference system fails?
When wondering at the lack of diversity (in terms of race or international participation (is this a problem?)) in our field, is this one of the causes? Or, to think about this more generally, is lack of access to electricity and electronics still causing our field to remain "small?"

Here, in the nation's capital, I'm reveling in the fact that the lights are on and so is my computer.

Sensor Data Sets

2010-04-13T17:52:00.003-04:00

As part of some recent work, I've been looking around online for data sets of moving objects. I've come across some incredibly useful ones, some incredibly boring ones, and some horribly maintained ones. I'm not going to talk about any of those today. Instead, I present here the ones that made the process amusing/exciting/interesting. Of course, some of these also turned out to be useful. None were boring.

The Owl Project: MIT Media Lab: Strap cell phones to trees in the forest. Program the cell phones to sound like owls when they ring. Call the cell phones. Record the responding owl hoots.
Moose Research: Watch moose movements on online maps. Aren't moose just always funny?
Finding a Cab in NYC: Are you constantly standing confused on a street corner in NYC wondering where all the cabs are? Do you live in Queens? A cell phone app can let you know what street corners near you had the most cab pickups at this time/day. It can also show you that you really can't get a cab in Brooklyn.
Birds with Backpacks: The picture above really says it all.

Reminders

2010-04-12T16:55:00.002-04:00

The ESA 2010 deadline is tonight at midnight Honolulu time.

The MASSIVE 2010 deadline is Wednesday.

Science Skeptics

2010-03-19T13:43:00.001-04:00

I have had the rare occasion recently to discuss "controversial" science with non-scientist skeptics (read: family). I generally avoid politics and other such topics (the old "no politics or religion" plan), but naively thought that I would be safe discussing global warming. I was wrong.

Now, perhaps I should first comment that in some ways it's good that people are skeptical. It shows an engaged mind unwilling to be brainwashed. The family I was talking to have read up in great detail (more than I have, certainly) on global warming and know all the "arguments" against believing that it's human-caused. They've probably even read some "scientific" papers on the subject, and are generally unwilling to believe that something is true just because a newspaper says so (something that would have been welcome during the "there are WMDs in Iraq" era). And because they do take the time to learn about such topics, they don't fall victim to some of the more ridiculous anti-science theories (ahem: vaccines). But in the case of global warming, their skepticism isn't serving truth.

Why not? I believe the main reason is because of the scientific complexity of the issue. I certainly can't understand, in great detail, all of the arguments making the case that human actions are causing global warming. And I'm used to reading scientific papers. Obviously then, it's much harder for a non-scientist to understand the arguments. And how can you believe something you can't understand? Of course, politicians and oil companies (and politicians paid off by oil companies) are all preying on this to try to convince the world (non-scientist) public that those scientists are making everything up.

So what can we do? I'm actually glad that I stumbled into this argument, though it goes against my policy of "no politics or religion" with family. I think it's important that, as scientists, we stand up for science. Science needs better PR, and a good way to start is for all of us to take the responsibility of confronting the skepticism of people who already trust us.

Sophie Morel

2010-03-11T13:37:00.003-05:00

While doing a book review of Change is Possible: Stories of Women and Minorities in Mathematics by Patricia C. Kenschaft (I'll talk about the book itself some other time) I came across this gem: the Harvard mathematics department has never had a tenured female member. The book was written in 2005, so I checked the Harvard website to see if anything had changed. It hadn't. But that was a few months ago.

Hidden away in this article about women at Harvard was this history-making news:

And at Harvard, as at most American research universities, math and science remain male domains. The math department’s first tenured woman, Sophie Morel, arrived just three months ago. The department admitted two female graduate students this year and none last year.

Harvard, the oldest institution of higher learning in the US, was founded 374 years ago.

Women in Science Overview

2010-03-08T10:55:00.003-05:00

There's a nice article in the NY Times giving an overview of the state of women in science worldwide (though with a definite focus on the US and Europe). Computer science is, as usual, given as an example of one of the lone hold-out fields where women are still sorely outnumbered. The article focuses on academia (without ever explicitly saying that's what it's doing).

A nice summary section:

The tug-of-war between encouraging numbers and depressing details is in many ways the story of the advancement of women overall. Women get more degrees and score higher grades than men in industrialized countries. But they are still paid less and are more likely to work part time. Only 18 percent of tenured professors in the 27 countries of the European Union are women.

And the big money in science these days is in computers and engineering — the two fields with the fewest women.

My main complaint with the article, or really with this type of press, is that while pointing out many of the reasons that women are still in the minority (lack of childcare, the tenure clock coinciding with the biological one, etc.), it also seems to reinforce these ideas by interviewing women who have faced these issues or framing women who haven't as being "lucky" or having overcome them. Perhaps this is true, and it is after all an article, not an advertisement (as I'd like everything to be), but I do wish that such articles would be sure to find some women to speak with who believe in the positive role that academia can play in their and their family's lives (I see the time flexibility as the big one).

But overall, if you're interested in these issues, or interested in an easy-to-read summary to get you up to date on the broad issues, this is a good one. (If you have a broader interest, the sidebar of the article leads to a yearlong series on women.)

Job Searching Comrades

2010-02-25T15:43:00.003-05:00

You may have noticed that I haven't been blogging much. All I can think about is the crazy job market. And it's the one thing I really shouldn't be blogging about since I'm in it. Hence, silence.

But here's one thing I can say: It'd be great to commiserate with others out there! Of course, there's always the wiki, but it's never the same as actually meeting other folks. Plus, it's been wonderful meeting people from various departments as part of all of this - and I suspect the other applicants would also be interesting and exciting computer scientists to talk to. In this regard, I'm a bit jealous of the search committees who get to meet us all. To add to the discussion on our community's conferences going on at Michael's page, this is another reason that having more of a flagship conference might be nice.

Until then, feel free to comment here or email me separately to say hello online.

SoCG 2010 Accepted Papers - Motion

2010-02-16T09:53:00.004-05:00

Suresh has posted the SoCG accepted papers (they don't seem to exist anywhere else yet).

Here are the (obviously) motion related papers. I couldn't find pdfs online of any of these - if you have links, please leave them in the comments. Exciting that there are so many this year! Sad that 4 is a lot.

Pankaj K. Agarwal, Jie Gao, Leonidas Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin and Micha Sharir. Kinetic Stable Delaunay Graphs
Haim Kaplan, Micha Sharir and Natan Rubin. A Kinetic Triangulation Scheme For Moving Points in The Plane
Bernard Chazelle. A Geometric Approach to Collective Motion
Bernard Chazelle. The Geometry of Flocking

Second Women in Theory Workshop

2009-12-16T23:09:00.002-05:00

This blog has its origins in an excellent workshop for women in theoretical computer science that I attended in the summer of 2008. Happily, it's happening again! Not only did I learn a lot from the technical talks and have fun networking with the women there, but the networking has been successful in the longer-term as well. One of the sometimes frustrating things about general women in computer science conferences is that you meet wonderful people who you can't look forward to seeing at technical conferences. This workshop is satisfyingly different in that way. I definitely recommend going.

Now, the more formal announcement (from Tal Rabin):

We will be holding the Second Women in Theory Workshop at Princeton on June 19-23, 2010.
To apply please go to:
http://intractability.princeton.edu/blog/2009/11/women-in-theory-2010-workshop/
The format will be similar to the WIT 2008 workshop. You can view information on that workshop at:
http://www.cs.princeton.edu/theory/index.php/Main/WIT08
and view a video of WIT08.

Drugs - Less Scary Than Science

2009-12-13T20:47:00.004-05:00

A lovely article on Sally Ride and what she's doing to try to encourage kids to like science includes this gem:

A study by the silicon chip giant Intel showed that parents are more willing to talk to their children about drugs than math and science.

Really? That can't be right... let's look at that quote again:

A study by the silicon chip giant Intel showed that parents are more willing to talk to their children about drugs than math and science.

Yes, really. Drugs are less scary than math and science (at least in the US). News drug dealers all over the country are I'm sure excited to hear. It's a result of their successful campaign to recruit friendly drug pushers. No? It's a result of the declining science education in this country? (Just my speculation here, folks.) Oh, well that could be true too.

Other than the absurd, the article's main points are:

The economy will suffer if the next generation doesn't have a strong science education.
The next generation will suffer if they don't have a strong science education.

The second point is, of course, directly related to the first.

And so ends National Computer Science Education week. Now go talk to your kids about drugs.

National Computer Science Education Week

2009-12-10T14:29:00.006-05:00

You may not have noticed, but this week is National Computer Science Education Week, a week dedicated to increasing the amount of computer science education (especially in high schools). In this spirit, I looked up the US government projections about computer science occupations in 2018 (ten years from the last time they did this analysis). Unsurprisingly, the number of computer science related jobs is expected to increase. Drastically. The subsection with the most increase is "computer software engineers, applications," which is projected to increase by 34%. The total number of new jobs projected is approximately 450,400. In contrast, the Taulbee Survey shows that the total number of bachelor's degrees awarded in computer science and computer engineering in 2008 was 12,815. In other words, if these levels of new graduates continue (and all take jobs in computer science and no other applicants enter the field), there will be 322,250 jobs unfilled, or more than two-thirds of the newly created jobs.

Of course, the US is not a self-contained system, and neither is our field. Still, perhaps it's worth remembering the statistics when chatting with the dean about department growth...

SoCG Deadline

2009-12-02T14:01:00.002-05:00

The SoCG 2010 paper submission deadline is today. Good luck folks!

Is DC Mature?

2009-11-20T14:49:00.002-05:00

I was taken by surprise by an article about the new proposed Home Rule Act. Not because of the thing that should be shocking - the lack of a right to self-governance in the nation's capital - but because of the reasoning behind it, a historical perspective that I was ignorant of.

In more than two hours of testimony, Fenty and Gray told a congressional subcommittee that the city and its leaders are now mature enough to lose some of the congressional scrutiny established under the Home Rule act. [emphasis mine]

First, let's remember what we're talking about here: all DC laws, budgets, etc., must be approved by Congress before they can become law. The new act would not loosen restrictions much, it would still allow Congress to overturn laws passed by the district, it just wouldn't require congressional approval to pass them in the first place. And all of that is, I believe, obviously ridiculous. But what I noticed here was more about the attitude, present in the word choice, that led to these laws seeming necessary/reasonable in the first place. It's about the city and its leaders being "mature" enough to handle democracy, "mature" enough to handle truly having a right to vote. In a majority black city, it seems clear why some congressmen still think the city deserves separate treatment. Perhaps as the population changes, and the city becomes more white, it will suddenly be seen as "mature" enough.

FWCG '09 and the CRA-W/CDC Workshop

2009-11-16T17:46:00.029-05:00

I'd never been to the Fall Workshop on Computational Geometry (FWCG) before - what a mistake! The workshop, held this year at Tufts University, was excellent. Papers presented at the workshop can be submitted elsewhere, it's less a publication venue than a true chance to share information (in short 15 minute bursts). This year it was held in conjunction with the CRA-W/CDC Workshop on Computational Geometry, which featured 45 minute talks by the experts.

The 15 minute talks at FWCG were a whirlwind of interesting topics. I'll post about my talk some other day and instead discuss the CRA-W workshop here. For me, the theme of the CRA-W workshop seemed to be "those questions you've always wondered about." Godfried Toussaint's talk even began with that hook, though I imagine it only rang true for a few of us. He discussed the geometry of rhythm as part of an effort to identify the lineage of rhythms. Imagine that the repetitive underlying rhythm (in Cuba this is the clave, in Ghana it's known as the bell) is represented as points around a circle, then the rhythm can be analyzed in the form of the shape created by connecting these points. The talk right after that, by Anna Lubiw, discussed questions of shortest paths under various restrictions. For example, while only walking uphill, or, as I frequently wonder while canoeing, the shortest path based on the wind and currents.

All in all, an excellent way to spend a weekend. Definitely worth going to even if it's not local for you. And a reminder of what our conferences could all be like in an ideal world.

Clustering Over Space and Time

2009-10-28T17:30:00.000-04:00

(This is partially in response to Suresh's wonderful series on clustering.)

Recently, my advisor (Dave Mount) and I have been kicking around the idea of how to define the problem of clustering over time. Imagine birds traveling in a flock from Canada to Mexico, and suppose that you are able to perfectly observe their locations over time (of course, for any practical use we'd need to come up with a better model, but for now...). Given all these locations, you'd like to be able to identify the flock as a cluster. If this flock crosses another flock (say, stupidly traveling from California to Maryland), you'd like to be able to identify these as two separate flocks, even if the "current" time is the one at which they're all in the same place.

Now, what about if the birds' pattern is a bit more complicated... Suppose that instead of staying nicely within the same approximate radius as they fly, the radius of the cluster varies drastically. Perhaps all the birds fly away from each other for some amount of time, then converge back to a central point, then fly away again, etc. Or perhaps there are many flocks all flying from Canada to Mexico that follow parallel linear paths, but spaced many miles apart. Are these clusters that we want to identify?

These are certainly questions that biologists are interested in (understanding infections over time), as well as folks in data mining and statistical modeling (general ideas about changing data over time). I've seen algorithmic approaches about clustering data streams (Cormode, Muthukrishnan, and Zhuang) or kinetic data structures models that maintain a clustering snapshot (Gao, Guibas, and Nguyen, and my own work) and database papers about essentially this question (Kalnis, Mamoulis, and Bakiras), but haven't seen algorithmic approaches to this question. So, I ask the internet, are there any papers I should know about? Anything else I should be thinking about?

National Computer Science Education Week

2009-10-26T12:08:00.004-04:00

Last week, Congress (trying to push off health care reform for as long as possible) passed house resolution 558 to create national computer science education week, the week of December 7th. Why the week of December 7th? Grace Hopper's birthday was December 9th!

If these statistics (from the ACM) are still accurate, then we're badly in need of more computer science education. Talking with a friend about this recently, I found myself defending the position that computer science is not so hard that many more people can't learn it. Though originally a devil's advocate position, I talked myself into believing it. While it's unreasonable to expect that many people could get Ph.D.s in computer science, it does seem reasonable to expect many people to be able to understand basic algorithms and master basic programming skills. And that needs to happen. As money leads, so people will follow. Or, people will follow if the government leads. The government's encouragement is nice, but not actually transformative unless they put muscle behind it - perhaps a mandate for computer science education in high schools, or at least less focus on NCLB testing so that schools can teach subjects other than math and English. Meanwhile, we can all do our best to lure unsuspecting freshman to our classes with robots, videos, and other shiny things.

Conference Roommate Finding Forum

2009-10-21T10:02:00.000-04:00

Announcing a conference roommate finding board: http://conferences.proboards.com/.

The hope is that this will help students (and others) to find roommates to share hotel rooms with at conferences, thus decreasing cost and increasing the possibility of attendance. Ideally, I think this is something that should be hosted by CRA or ACM, but until they take over, it seems better to have something than nothing. Similarly, I don't intend this to be limited to theoretical computer science.

Please spread the word so that it will actually be useful!

On the Job Market

2009-10-19T11:00:00.000-04:00

Having just sent off a bunch of applications, it seems fair to say that I'm officially on the job market. I'm planning to graduate this coming summer. Given the current market, I'm applying to all sorts of jobs - academia, labs, industry, permanent, 2-year, etc. I'd love to end up somewhere with exciting colleagues, interesting research possibilities, engaged students, and amazing things to do on the weekends... but I'm cursed with a certain dose of realism. Still, if you know how to achieve all my dreams, I'd love to hear the advice. Or, of course, if you have job tips...

(For more about who I am and what I do, see my more professional site.)

SoCG 2010 Call for Papers

2009-10-09T20:44:00.003-04:00

The call for papers for SoCG 2010 just went out. It's in Utah, and Suresh is one of the local organizers. Plus, last I heard I'll be helping out with a student-only get to meet each other event. So you have just under two months to solve a problem and write a paper! Since it looks like the call hasn't appeared on the website yet, I'm including the basic details below:

-----------------------------------------------------------------------
CALL FOR PAPERS, VIDEOS, AND MULTIMEDIA
-----------------------------------------------------------------------
26th Annual Symposium on Computational Geometry (SoCG 2010)
June 13-16, 2010
Snowbird, Utah, USA
In cooperation with ACM SIGACT and SIGGRAPH

http://www.sci.utah.edu/socg2010/

The Twenty-sixth Annual Symposium on Computational Geometry will be held at Snowbird, Utah. We invite submissions of high-quality papers, videos, and multimedia presentations describing original research addressing computational problems in a geometric setting, in particular their algorithmic solutions, implementation issues, applications, and mathematical foundations.

The topics of the Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:
* design, analysis, and implementation of geometric algorithms and data structures; lower bounds on the computational complexity of geometric problems;
* mathematical, numerical, and algebraic issues arising in the formulation, analysis, implementation, and experimental evaluation of geometric algorithms and heuristics; discrete and combinatorial geometry; computational topology;
* novel algorithmic applications of geometry in computer graphics, geometric modeling, computer-aided design and manufacturing, scientific computing, geographic information systems, database systems, robotics, computational biology, machine learning, sensor networks, medical imaging, combinatorial optimization, statistical analysis, discrete differential geometry, theoretical computer science, graph drawing, pure mathematics, and other fields.

----- Important Dates -----

* November 23, 2009: Paper titles and (short) abstracts due
* December 02, 2009: Full submissions due (23:59, Honolulu time)
* February 15, 2010: Notification of acceptance/rejection of papers
* February, 19, 2010: Video and multimedia submissions due
* March 01, 2010: Notification of acceptance or rejection of video/multimedia submissions
* March 15, 2010: Camera-ready papers and video/multimedia abstracts due
* April 20, 2010: Final versions of video/multimedia presentations due
* June 13-16, 2010: Symposium at Snowbird, Utah

----- Local Arrangements Co-Chairs ------

* Valerio Pascucci (University of Utah)
* Suresh Venkatasubramanian (University of Utah)

---------------------------------------------------------------------
CALL FOR PAPERS
---------------------------------------------------------------------

We invite submissions of high-quality papers describing original research on geometric algorithms and data structures, their mathematical foundations and correctness, their implementation, and their applications.

The program committee explicitly encourages the submission of video or multimedia in support of submitted papers. Authors may wish to consider making a separate submission to the video/multimedia track (see the guidelines below). Papers and video/multimedia submissions will be reviewed separately; acceptance or rejection of one will not influence acceptance or rejection of the other.

Final versions of accepted papers will be published by ACM in the symposium proceedings. Proceedings will be distributed to symposium participants and will also be available from ACM for purchase or through the digital library. An author of each accepted paper will be expected to attend the Symposium and give a presentation (approximately 20 minutes) of the paper. Authors of a selection of papers from the conference will be invited to submit extended versions of their papers to a special issue of one or more journals.

Grace Hopper 2009

2009-10-06T09:50:00.013-04:00

I just got back from Grace Hopper in Tucson! Some highlights:

The keynote by Megan Smith, VP of New Business Development and General Manager of Google.org, was excellent. She showed us a map of the world highlighted based on the number of search queries from the region (I wish I could find the map, it was definitely worth seeing). Africa was mostly empty of queries in comparison to the rest of the world. One of the things I really appreciated about her description of ways to change that was her acknowledgement that the people of Africa are highly intelligent and will "bring the internet to themselves."
I went to a talk about feminism and technology. The highlight was a Skype'd in call from a woman in Pakistan. She discussed how technology is increasing women's freedom to work, even if they aren't allowed to leave their homes. It was amazing to see her, and the room was packed.
The Best Practices in Introductory Computer Science Classes talk had some excellent and exciting ideas. My favorite suggestion (or really, theme) was the idea of taking projects that local community organizations need done, and giving them as class or group projects to the students. This motivates the students to do their best, since people are actually relying on what they get done, and also helps local organizations that frequently need small programs written but don't have the money to hire a programmer. While this might not work in an algorithms class, it seems like a good fit for a second or third programming focussed class.
I stayed for the weekend after Grace Hopper to go hiking and get to see more of Tucson than just the hotel. I went with a friend who I met at the CRA-W Grad Cohort my first year of grad school. We're still friends and both still in grad school, so for a sample size of two Grad Cohort has been effective. We spent Saturday hiking in the desert, and Sunday exploring the surrounding mountains. Saturday evening we went to watch the sunset in a location suggested by one of the rangers, and were treated to a beautiful sunset, full moon, and group of people singing the sun to sleep. Apparently Tucson doesn't frequently have clouds, but that certainly wasn't my experience.
Of course, no trip to Tucson is complete without cacti.

All in all, an excellent trip.

LATIN deadline

2009-09-24T16:24:00.002-04:00

Just a reminder that the (extended) LATIN deadline is on Monday at 4pm EDT. Given the size of the PC, you probably already knew that.

Absurdist Headlines

2009-09-23T23:49:00.003-04:00

Sometimes these days when I read the news (on Salon), I wonder if I'm actually reading the Onion... but really, you can't make this stuff up:

Group Work

2009-09-16T15:21:00.002-04:00

I spent a lot of in-class time doing group practice exercises during the class I taught this summer (for ruminations on summer classes in general, see this paired post). I just got my teaching evaluations back, and it looks like the students and I agree - group work was a success. To paraphrase my students, having to explain your thought process to others helps you to learn the material, plus the skills and experiences necessary to work in groups will be useful to have in the workplace. It also breaks up the in-class time so that everyone (teacher included) can use their brain in a different way and avoid that lecture class stupor. And while it does take more thought to prepare this kind of class, I'm not convinced that it actually takes more time.

So what is this group work thing I'm talking about? I did group work in three forms with my class this summer:

Short, straightforward exercises reinforcing what we just talked about, done on their own or with the people sitting near them, usually lasting about 5 minutes. After introducing an algorithm and doing a sample run of it on the board, I would often give another input instance and ask the students to run the algorithm again.
Longer, more difficult exercises applying the topic of the day with the aim of making sure all students can see a typical (easy) problem on this topic through from beginning to end, done in groups of about 4 at the boards around the classroom, usually lasting about 20 minutes, with me walking around and talking them through it when they get stuck. For example, proving that a problem is NP-complete.
Out of class group project - I'm putting off a full explanation of this project until a later post, but in short, they were asked to work in groups of 2 or 3 on a 3-week long (out of 6 weeks) in-depth project.

Practice exercises in class - isn't that what discussion sections and homework are for? Yes (though this class didn't have a discussion section). But making sure the students understand the material is important enough to do multiple times, don't you think? In fact, most algorithms classes take the time to run the algorithm on sample input, it's just usually done by the professor at the board. So it doesn't actually take much more time to have the students work on it together, but it seems to me that they're much more likely to understand it if they had to do it themselves than if they watched you (and maybe a few of the more outgoing members of the class) do it on the board. Also, as the teacher, it gives you a chance for some mental breathing space, and a chance to find out what your students are struggling with instead of just guessing.

So, are you convinced? Already a fan? I'd be interested to hear other folks' experiences and suggestions.

New (Woman in Theory) Blog!

2009-09-11T15:49:00.003-04:00

Congrats to Cora Borradaile on her new job (at Oregon State) and accompanying new blog. Welcome to the blogosphere!

(Thanks to David E. for the news.)

SODA accepted papers list

2009-09-04T08:43:00.003-04:00

The SODA accepted papers list is here (as previously noted). From the titles, there seem to be lots of potentially geometry-related papers, but the promised abstracts should make that clearer.

It's Not the Heat, It's the Stupidity

2009-09-02T11:20:00.001-04:00

(Guest post by Bill Gasarch. Companion post at his blog.)

***SORELLE*** taught undergraduate algorithms in summer of 2009. I proofread her midterm, proofread her final (resulting in one question being taken off and replaced), and sat in on it (at her request) so I could see what's up. This is as good an excuse as any to talk about summer courses, and to have us guest post on each others blogs.

Is taking classes over the summer a good idea? Jamming 15 weeks into 7 weeks might make the class go fast, though if its the only class you are taking and you care about the material, this can work. If you failed it in the regular term and need to catch up and will really put the work in then that can work also.

(Personal note: I took four summer courses as an ugrad: Summer after freshman year I took multivariate calculus and Prob, Summer after Sophomore year I took Physics II and Basic Anthropology. It worked for me, but note that I cared about these subjects.)

Is teaching a class over the summer a good idea? I'll defer to ***SORELLE'S*** post for that one.

Summer courses tend to have an inverted bell curve. There are some very good students who want to get ahead. There are some very bad students who need to catch up. There are less in between.
***SORELLE*** was doing a review for the midterm. This was challenge since some of the students didn't know basic induction. So she had to walk it back to material in courses that were two courses ago! Should she have ignored those students and concentrate on the good ones? The ones that don't need review? How about the middle? I'll let her answer those thoughts.

Recommendation Letters

2009-08-17T14:03:00.003-04:00

A few years ago I read a NY Times article that has stuck in my mind. I'm not sure if I found the same article, but I did find two that had similar points to make. Here are the relevant sections:

Women in Science: The Battle Moves to the Trenches

Dr. Steitz cited a study of letters of recommendation written for men and women seeking academic appointments. Though all the applicants were successful, she said, and though the letters were written by men and women, the study found that the applicant’s personal life was mentioned six times more often if the letter was about a woman.

Also, Dr. Steitz said, “For women, the things that were talked about more frequently were how well they were trained, what good teachers they were and how well their applications were put together.” When the subject of the letter was male, she said, the big topics were research skills and success in the lab.

For Women in Sciences, Slow Progress in Academia

Mel Hochster, a mathematics professor at Michigan, belongs to a committee of senior science professors that gives workshops for heads of departments and search committees highlighting the findings of numerous studies on sex bias in hiring. For example, men are given longer letters of recommendation than women, and their letters are more focused on relevant credentials. Men and women are more likely to vote to hire a male job applicant than a woman with an identical record. Women applying for a postdoctoral fellowship had to be 2.5 times as productive to receive the same competence score as the average male applicant. When orchestras hold blind auditions, in which they cannot see the musician, 30 percent to 55 percent more women are hired.

It's the letter writing bias that I'm interested in here. I haven't found any research to back this up, but I believe that letter writing also shows unconscious racial bias as well as gender bias. For example, letters for my Latino friends emphasize that they're "laid-back" and easy to get along with instead of emphasizing their intelligence, research success, etc. While being easy to get along with is certainly a good trait, perhaps even one that belongs in one paragraph at the end of a letter, it should never be the focus of a recommendation letter - it should not be emphasized over the research accomplishments of the applicant. Letter writers often hold back women and minority applicants by their, often unintentional, lack of emphasis of the skills necessary for the job.

Yet it's so easy to fix! After all, a recommendation letter need not be subject to societal biases - there are many chances to read it over to correct for these, and the writer may try anew for each new letter. And so, as I prepare to enter the job market, I encourage all of you who may be writing letters (for me or anyone else) to examine your letters through this lens, and make sure you're expressing an appropriate evaluation.

Numb3rs Algorithm Clips

2009-08-10T12:23:00.007-04:00

One of the things I've been enjoying doing while teaching Algorithms during this summer session is including algorithm explanations from Numb3rs whenever possible. Unfortunately, due to copyright constraints, I can't share the actual clips with all of you, but I can at least tell you where to find them. (My limited understanding of the copyright law is that since I bought the episode - $2 from iTunes - I can show short clips for educational use in my classroom. I could be wrong, so proceed based on your own understanding.) Here are the clips by algorithm/problem, episode, title, and approximate time within the episode.

Art Gallery Problem - Season 2, Episode 3, Obsession. 9:05 - 9:20. This is unfortunately a very short clip that doesn't really give a statement of the problem.
Dijkstra's Shortest Path Algorithm - Season 3, Episode 23, Money for Nothing. 9:20 - 10:10. This gives a nice description of greedy algorithms in general (via the change algorithm, though without David E's more detailed comments) and an overview of Dijkstra's algorithm.
Knapsack Problem - Season 3, Episode 24, The Janus List. 18:30 - 19:00. This clip gives a nice and mostly compete description of the problem in the context of "things you would bring on a hiking trip" based on weight and their importance.
P vs. NP - Season 1, Episode 2, Uncertainty Principle. 18:30 - 19:00. The P =? NP problem is a theme running throughout this episode... but unfortunately there's no nice clip that summarizes the problem, just lots of shots of Charlie working hard and a mention of the Minesweeper Consistency Problem. The specific times I mention are as close as I could find to a useful clip for teaching purposes.
Monty Hall Problem - This is a clip that's actually on YouTube, so I'll let whoever posted it take the blame for the copyright issues and just give a link.
The Seven Bridges of Konigsberg - Season 2, Episode 9, Toxin. 24:30 - 25:20. If you imagine that this problem would look beautiful if well-animated and described, you're right.
Voronoi Diagrams - Season 2, Episode 10, Bones of Contention. 29:45 - 30:25. A description of Voronoi diagrams in terms of "the closest place to find a cheeseburger."

I've been thoroughly enjoying watching these clips in class, and I think my students have too. Perhaps this will become a running series as/if I find more. If you know of any additional clips, from Numb3rs or elsewhere, please leave them in the comments.

Purple With Glee

2009-08-04T16:20:00.006-04:00

The (Maryland portion of the) purple line, the mythical creature of DC, much spoken of and never seen, took a step towards reality today. Maryland governor O'Malley announced his support for the light-rail version of the line (much preferable to the bus rapid transit version) and his intent to apply for federal funding. Getting to this seemingly insignificant step has taken forever since there's been a lot of resistance from (rich, white) locals in Montgomery County (who don't ride public transit anyway) who are upset that the Metro will run through a local park (that wouldn't exist if it weren't for the existing right-of-way).

Any of you who attended STOC (held in Bethesda) and had some desire to visit U of Md at College Park may have noticed how exceedingly inconvenient that was by public transit. Now look at the proposed map and imagine my glee should this ever actually be built (long after I have already graduated).

Who Cares If They Learn?

2009-07-27T15:48:00.001-04:00

One of the commenters had this to say in response to my post awhile back on interactive teaching:

The "math class" approach you describe is for babies. It is the students' job to do this on their own, or have the TAs cover it in section.

With these approaches you cannot cover as much material. It is style over substance. But if you are going slowly and not trying to cover much material, I suppose it can't hurt.

Ignoring* the phrasing, the point here is one that I've heard many times - that somehow you do your students a disservice if you actually take the time to teach them the material. I believe the root of the disagreement is based in whether or not you believe that your job is to teach the material, or just present as much as possible. While I certainly don't believe it's my job to make the students to try to learn (in other words, if they don't do the homework there's only so much you can do), I do believe it's my job to actually teach the material. Yes, this involves doing examples in class. Ideally, I think it also involves doing your best to keep your students from falling asleep in your class, however early in the morning it might be. I think students learn best by interacting during class (plus it keeps them awake). And it's not just me that thinks this (see Freire, Dewey, Piaget, or generally constructivism).

I'm trying to teach in this style during the Algorithms summer term class I'm currently in the middle of. Unfortunately, I'm partially falling victim to the second argument - "but if you take the time to teach, you won't cover as much." Even though I fundamentally disagree with it (assuming that you want the students to actually learn the material, taking the time to teach it is never wasted), I can't figure out a good way to teach the vast number of algorithms that I think I'd be doing a disservice if I didn't teach, and still spend long enough on each one so that they really understand the underlying details. (This is made especially hard since the class meets every day, so there's no time for contemplation between classes.) I'm doing examples in class, having discussions about the algorithms, having them try sample instances, etc. Yet my idealist nature is somewhat unsatisfied.

On the other hand, I've assigned a half-term long programming project that does embody these values and which I'm very excited about. More on that later.

*Actually, I can't quite bring myself to ignore it altogether. While I'm glad not to be seeing a Barbie-style "math is hard," the idea that anything having to do with math class is "for babies" is rather absurd. Some things that are for babies; diapers, bottles, toys, mushed carrots. Things that are not for babies; Calculus, Algorithms, going to college, taking my classes.

Happy Moon Landing

2009-07-20T16:49:00.003-04:00

To mark the 40th anniversary of the moon landing, I want to bring up an article that marked the 50th anniversary of Sputnik (very un-American of me, I know). It was about how Sputnik spurred a new era in science education in this country. While many still speak of "new math" with derision, it was part of a wave of changes that energized science education and changed the way students thought about science. Science was no longer about boring equations, but about space and sending a man to the moon! Unfortunately, we've been on a downward spiral since the end of the cold war. It no longer seems urgent to understand science. It no longer seems exciting. And without the "red menace" to spur us on, we've become complacent. Perhaps some of the blame goes to the government, for mandating testing yearly only in Math and English. But there's plenty of blame to spread around. The curriculum is "too hard" for the students when it's interactive - or maybe just "too hard" for the teachers. Interactive teaching takes too long. All the bright scientists make more money not teaching. The list goes on. But something needs to be done. I imagine that every computer scientist has experienced the shock and awe and terror that accompanies admission of our job. It's just a symptom of the larger problem. And while perhaps science will never be (and should never be?) easy, it should certainly be exciting. After all, someone needs to create the next imagination-inspiring "moon landing."

A Sensor-Based Framework for Kinetic Data

2009-06-29T11:59:00.006-04:00

I leave in about a week for Greece, where I'll be presenting a paper at AlgoSensors, a workshop associated with ICALP. The paper is entitled "Compressing Kinetic Data From Sensor Networks" and is joint work with my advisor, David Mount. You can see the camera ready version here. Slides will be posted on my website once they exist.

While the main result of the paper is a compression algorithm, the point of the paper is broader than that. When reasoning about kinetic data (the data generated by a set of moving points), the current accepted model is the kinetic data structures model that assumes that points are given flight plans in the form of algebraic expressions. This works well when reasoning theoretically (assume the points follow predetermined algebraic curves...), when modeling physical properties, or possibly when dealing with actual planes that really do need to give us their flight plans in advance. But what about if we want to do statistical analyses on collected data to determine what motion trends the objects follow? The cell phone users, migratory birds, enemy tanks, whatever you like to think about, aren't going to tell us how and when and where they're going to move. Many of these observations are collected using a sensor network, so it makes sense to design algorithms that work over these networks using the possible minimal amount of information available - the number of objects each sensor sees at each time instant. The framework we introduce assumes nothing about the motion of the objects or our advance knowledge of their plans. Instead, we analyze our results with respect to the entropy of this information. The ultimate goal, then, is that algorithms designed over this framework would perform better on "neat" motion, say all the birds following a straight line from Canada to Mexico, while algorithms on "messy" data would take longer. This paper takes the first step in that direction, giving a compression algorithm that compresses the sensor observations to within a constant factor of the optimal joint entropy bound.

For those interested in more precision, the abstract is included below:

We introduce a framework for storing and processing kinetic data observed by sensor networks. These sensor networks generate vast quantities of data, which motivates a significant need for data compression. We are given a set of sensors, each of which continuously monitors some region of space. We are interested in the kinetic data generated by a finite set of objects moving through space, as observed by these sensors. Our model relies purely on sensor observations; it allows points to move freely and requires no advance notification of motion plans. Sensor outputs are represented as random processes, where nearby sensors may be statistically dependent. We model the local nature of sensor networks by assuming that two sensor outputs are statistically dependent only if the two sensors are among the k nearest neighbors of each other. We present an algorithm for the lossless compression of the data produced by the network. We show that, under the statistical dependence and locality assumptions of our framework, asymptotically this compression algorithm encodes the data to within a constant factor of the information-theoretic lower bound optimum dictated by the joint entropy of the system.

Also, a reminder - the SODA abstract deadline is today at 4:59pm EDT.

At The Lake

2009-06-19T12:11:00.003-04:00

It's the middle of my yearly pilgrimage to Minnesota lake country. It's beautiful here, and while I'm spending much of my time working, at least I'm looking at the lake while doing it.

I'm also reading an excellent book: How the States Got Their Shapes by Mark Stein. While I'm always skeptical about books on somewhat academic subjects written by non-academics (I think he's a playwright), it's a thoroughly enjoyable book that gives a brief overview of the history, geography, and geometry of state boundaries. As I like all three of those things, I'm totally hooked. It turns out that many of the decisions about state boundaries were made based on two main ideas - water rights and state equality. For example, why does Minnesota have the northeastern corner, known as the arrowhead, in which I am currently looking at a lake? Why isn't that Wisconsin or possibly Canada? It's all about access to the Great Lakes and through them the Atlantic Ocean - the Minnesota arrowhead was shaped precisely so that Canada, Wisconsin, and Minnesota all have access to Lake Superior. On the other hand, why that specific boundary taking a southeast course from the Lake of the Woods to Superior? The book just says that it follows the boundaries of a set of lakes, but up here there are a whole lot of lakes. I have to wonder whether the boundary was really chosen to be where it is today, or whether no-one noticed or cared since the area was, and is, mostly uninhabited. The region is now part of an international/national park - the Boundary Waters Canoe Area Wilderness. The only way in is by canoe. I'll hopefully make a day trip in sometime next week.

Life Is Unfair - Sue

2009-06-08T20:10:00.001-04:00

I've been meaning to post this information for awhile - it was distributed (with right to forward) on the Systers email list in response to a question about what to do if you believe that you've been denied tenure due to discrimination.

One resource to recommend is the AAUW Legal Advocacy Fund.

LAF has a long history of fighting sex discrimination in higher education, and in 2004 published a summary of several cases in "Tenure Denied." Download the full report.

In the last couple of years, LAF has stopped providing support for individual plaintiffs, but it does maintain a network of attorneys who are experienced in such cases and willing to discuss options with potential plaintiffs.

See these resources for more information on tenure issues.

For those of you in a position to be more proactive, check out LAF's campus outreach program to bring a gender-equity focused program to your campus.

If you're female and you're not already on the Systers email list, I recommend it (though only in digest form... it gets a lot of traffic).

The Cost of Being a Woman in CS

2009-06-03T10:45:00.000-04:00

A paper of mine was accepted at AlgoSensors, which will be held in conjunction with ICALP this July. I'll post a summary and copy once the camera-ready version is finished. Right now, I'm working on the logistics of getting to and staying in Rhodes, Greece, an exciting but expensive location. The problem with staying at this conference, as with any conference, is that as a woman in computer science it's hard to find a roommate. The chance that another woman from your school is going is extremely small, since the chance that you're not the only woman in theory in your department is small to begin with. Perhaps this is why all the female students I talked to at STOC were staying with people they knew in the local area, while most of the male students were sharing hotel rooms. Were female students without local connections unable to afford to come? Knowing women from other schools due to the women in computer science conferences helps, but certainly doesn't solve, this problem. And so going to conferences costs (my advisor) more money than it should - more money than it would if I were male.

There is a simple solution to this problem. And, as in the case with many changes I advocate with women in mind, it would help men too (in addition to our advisors' budgets). CRA or ACM could put up an online conference roommate finding board. If one exists, I couldn't find it. Perhaps one of you has the ear of the right person...

In the meantime, if any of you know (or are) a woman going to ICALP and looking for a roommate for the nights of July 8th - 11th, please send her my way.

STOC

2009-06-02T15:02:00.006-04:00

Other folks already have some nice STOC summaries up (Bill/Lance, Michael), so I won't repeat them except to say that not only was Shafi Goldwasser's Athena Lecture excellent, her jokes were intelligent too (if you missed it, it looks like there might be a video posted here some day). Truly a talk worth seeing.

Another talk that's gotten less attention, but that I thought was exciting, was the paper "Homology flows, cohomology cuts" by Erin Chambers, Jeff Erickson, and Amir Nayyeri. There's no point paraphrasing when they say it so well themselves:

We describe the first algorithms to compute Maximum flows in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a maximum (s,t)-flow in in O(g7 n log2n log2C) time for integer capacities that sum to C, or in (g log n)O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

Check out their full paper from Jeff's site, where I also stole the nice graphic and abstract from.

I was volunteering for the conference (Maryland was the local host) and spent some of my time working the registration desk, which gave me a nice chance to see people as they entered. It was nice to meet some of you in person. Even though the business meeting was a bit tame (perhaps Chazelle should be given best paper awards at every conference to add entertainment value...), it seems to have been a successful conference. Congrats and thanks to all the organizers/speakers/PC members/etc.

Sotomayor Nominated

2009-05-26T12:32:00.004-04:00

Today Obama nominated Judge Sonia Sotomayor to the Supreme Court. She is Hispanic and female and grew up in Bronx housing projects. Unsurprisingly, much of the news focus has been on these three facts, not on her record or intellect, though the NY Times at least includes her intellect in its headline. But while Republicans have and will try to oppose her nomination based partially on their belief that since she is Hispanic and female and grew up poor she will always favor those defendants in her decisions (and rich white male court justices will favor...?). Perhaps it's better instead to base these assumptions on her substantial record on the Court of Appeals for the Second Circuit. The SCOTUSblog has overviews of these decisions (overview, part 1, part 2, part 3, part 4, links via Feministing), and it seems from my brief reading to be clear that she considers the case at hand and could be called a centrist because of this.

Interactive Teaching

2009-05-21T11:51:00.003-04:00

An op-ed in the Washington Post from Monday discusses "senioritis" as a symptom of bad (read lecture-style) teaching. This is, as usual, discussed in the context of high school teaching. But it seems to me that this is something college teachers should think about as well - not because I believe it's our job to go to any length to get students to care and pay attention, but because I think interactive teaching makes the subject matter more obviously interesting, and we all deserve that (and barely anyone does it).

I'm teaching the 400-level Algorithms class at Maryland this summer. It's obvious to me how to do interesting somewhat interactive lectures on the standard algorithm subjects, it's less obvious to me how to make these lessons truly interactive non-lectures. The "math class approach" of problems and presentations is certainly one option. But I'd love to do lessons more in the true spirit of "interactiveness." Any suggestions?

(While I'm picking your collective brains, I'm also trying to decide on a good textbook that's an actually readable reference that I can also take some homework problems from. I'm currently planning on Algorithm Design by Kleinberg and Tardos. Is there another book I should be seriously considering?)

Not Happy to be Right

2009-05-19T11:00:00.002-04:00

Back during the primary season, I wrote that I was skeptical about Obama's support for a woman's right to choose what happens to her own body. I have since campaigned for him, gone to his inauguration, and generally felt pleased with our country and his office. This weekend, Obama spoke at Notre Dame about "abortion." In fact, in this quote "abortion" seems to refer only to birth control and not to abortion, since no doctors are currently ever required to perform abortions (just like they're never required to do nose jobs or become foot doctors).

In his commencement address, Mr. Obama said he supported a “sensible conscience clause,” referring to legislative actions that allow doctors or other health care providers to withhold abortion or other services that conflict with their religious beliefs. But he used the opportunity to call for more diversity of opinion and respect for differences.

These laws are used to deny access to birth control for women who don't have access to other doctors or the resources to find them. It is these women that the government should be protecting, not doctors and pharmacists.

I also have worries with regards to the wording of these clauses. Are they truly blanket clauses for any "services that conflict with their religious beliefs?" I honestly don't know. But if they are: Are Muslims allowed to deny a binge drinker the service of having their stomach pumped? Or, less life threatening, are Mormons allowed to deny a patient access to migraine medications (many of which have caffeine in them)? Where is the line? And if this only refers to birth control, why is the line there? How did this religions conviction come to be more important than all the others?

Outrage, the movie

2009-05-13T12:34:00.002-04:00

I barely ever make it to the movies, but this past weekend I had the pleasure of seeing Outrage, a movie about outing closeted gay politicians, or more specifically, those closeted gay politicians who reveal their hypocrisy by voting against gay issues. It was interesting to see now, in the midst of a month of huge advances in marriage equality. As the NY Times noted in its movie review, the movie already seems outdated in terms of its urgency. The NY assembly recently passed a same-sex marriage bill: "'We do nothing revolutionary or extraordinary today,' said Richard L. Brodsky, a Democrat from Westchester County." And he's right.

Yet, of course, the movie is nowhere near outdated. After all, Florida Governor Charlie Crist recently announced his run for Senate. Crist is one of the politicians outed by Outrage. I admit that before seeing the movie I assumed that these outings were actually wishful thinking or rumors. In fact, all are highly researched newsworthy exposes with multiple independent sources confirming Crist's (and the other politicians') exploits. Plus, it being DC, there were whispers of "I know him" and "I saw him at a party I went to" throughout the movie showing. I'm convinced.

I'm also convinced that it makes sense to out these politicians, though I believe in privacy. The movie made a good case that maintaining their place in the closet encourages politicians to take extreme anti-gay positions. It's the adult version of a frequent middle school occurrence; "I just beat up that gay kid, so clearly I'm not gay myself."

If you're curious to learn more about closeted politicians or the guy (featured in the movie) who outs many of them, see his blog.

Women Bully. And?

2009-05-11T10:45:00.003-04:00

The current most emailed article in the NYTimes online is about women bullying each other in the workplace. It's written in the tone of an expose about the shocking fact that women bully each other.

It’s probably no surprise that most of these bullies are men, as a survey by the Workplace Bullying Institute, an advocacy group, makes clear. But a good 40 percent of bullies are women. And at least the male bullies take an egalitarian approach, mowing down men and women pretty much in equal measure. The women appear to prefer their own kind, choosing other women as targets more than 70 percent of the time.

Surprise! Or not. I don't find this at all shocking. Saddening, yes. Shocking, no. Nor do I think we need to hold workshops to keep women from bullying each other specifically. Yes, it'd be great to stop all bullying in the workplace. All of it, meaning the bullying by the men too. But you can't expect women trying to make it to the top in an already hostile workplace to abide by different rules than the men do. And given the backlash of affirmative action and the glass ceiling, it makes perfect sense that women bully each other more than they do men - it's the logical choice to try to take down the weakest of the group who are also seen as your direct competitors. It may not work well for you in the long run. After you eliminate all the other women, you're next (and while the men may be "mowing down men and women pretty much in equal measure," are they mowing them down proportionally or actually in equal measure?). Still, in the moment, to get to that next promotion, it's a logical choice. Thinking that women should act differently to help each other out is either naive or paternalistic.

Yet I don't think that bullying is necessary. And I'm glad that in academia in computer science there seems to be a much more cooperative community that happily gives advice at conferences and the like. But perhaps the bullying exists and it's me that's naive.

My XO

2009-05-07T10:58:00.003-04:00

I thought I'd add my two cents to the recent discussion about Kindles. Now, I've never seen a Kindle, or researched other readers, or even thought about getting one. But mostly that's because I already have an excellent solution - my XO. Plus, the money goes to an organization I believe in to help all kids have access to computers. True, the XO is marketed as a computer, and it is actually a computer (so if you're reading a paper and discover you should probably also be reading a paper they cite, you can go get it), but I find it most useful as a reader. Once you download a paper (from the web or a USB drive), you can flatten the computer. The screen is high resolution and easy to read off of even in sunlight, since you can turn off the backlight (a feature I wish all computers had). And you can rotate the screen... though I don't really know why you'd want to. Most importantly, since it's an actual computer, it doesn't have any of these strange PDF compatibility issues - it just opens the PDF.

Sadly, the folks at OLPC seem to have decided not to run the give one get one programs that give the public access to the XO during the whole year. Based on the past two years, these happen only in November and December to capitalize on the Christmas shopping season. But keep your eyes out, because in 2010 there's promise of a super cool new design and a reduction in price. Currently, the laptop costs $400 through their G1G1 program, $200 for the laptop, and $200 a tax-deductible contribution that gives a laptop to a child without access. I've thoroughly enjoyed reading in coffee shops with mine, knowing that if someone spills coffee on my computer it will probably still work.

Of course, my XO doesn't do some of the things that the Kindle does, like let you easily pay $10 for each book.

SODA Call for Papers

2009-05-06T15:28:00.002-04:00

In case you missed it, the SODA call for papers is up. Abstracts are due June 29th, full papers are due July 6th. Consider this your two month warning.

... And It Continues

2009-05-05T13:30:00.004-04:00

A local surprise: The DC council just passed a measure to recognize same-sex marriages performed in "other" states. Of course, DC is not actually a state, so Congress has 30 days to approve it. As with the recent almost-possibly-still DC Voting Rights Act, this means that Congress will have a chance to play to their pet agendas and ensure that DC residents are not given a chance at self-governance. If tea-bagging hadn't been appropriated, I'd suggest we all take our tea out to the river.

In less political news, the ALGOSENSORS 09 deadline is midnight PST today. It'll be held in conjunction with ICALP in Rhodes, Greece.

Good Surprises

2009-04-30T10:44:00.003-04:00

There has been a lot of good news in the news in the past month (well, if you ignore the swine flu, the economic crisis, the torture memos...). Mostly, I mean there have been a lot of surprising domestic political advances, mostly on gay rights, that make me happy enough that I can momentarily ignore that the swine flu was recently found in Maryland:

Same-sex marriage in Iowa via court ruling April 3rd
Same-sex marriage in Vermont via legislature April 7th
Same-sex marriage bill announced in New York April 16th
Specter becomes a Democrat April 28th
Same-sex marriage bill in Maine advanced for a vote April 29th
House passes hate crimes bill April 29th
Same-sex marriage bill in New Hampshire passes Senate April 30th

And in more local news, I received a U. Maryland dissertation fellowship for one semester of the coming year. That news came by snail mail in which I usually only receive bills...

WADS 2009 Accepted Papers

2009-04-23T11:28:00.002-04:00

WADS 2009 accepted papers are now up. Sadly, no abstracts included.

Continued Title IX Confusion

2009-04-21T11:03:00.002-04:00

Last week there was an article about applying Title IX to the sciences in the Washington Post. I'm only just now writing about it since while I found it to be a frustrating read, I couldn't figure out why. Yes, it's an article that I disagree with. But that in itself is not frustrating to me. I appreciate well-reasoned arguments, even if I'm on the other side. Therein lies the problem - despite its condescending and arrogant tone, the article is illogical and incorrect at times. The author seeks to make her point through alarmism and absurdism instead of through reason. Perhaps she would have benefited from more participation in the sciences.

The author opens with these lines: "What's good for women's basketball will be good for nuclear physics. To most Americans, that statement will sound odd." Quantum physics would seem odd too. Happily, oddness is not usually used as a tool for evaluation.

She describes Title IX as "the law that requires universities to give equal funding to men's and women's athletics." In fact, simply looking at the first paragraph of the Wikipedia article on Title IX would disabuse her of the notion that the law was meant to apply directly to or only to athletics:

Title IX of the Education Amendments of 1972, now known as the Patsy T. Mink Equal Opportunity in Education Act in honor of its principal author, but more commonly known simply as Title IX, is a United States law enacted on June 23, 1972 that states: "No person in the United States shall, on the basis of sex, be excluded from participation in, be denied the benefits of, or be subjected to discrimination under any education program or activity receiving Federal financial assistance." Although the most prominent "public face" of Title IX is its impact on high school and collegiate athletics, the original statute made no reference to athletics.

I'm unclear why she brings this issue up now (the Obama quotes she references are from October). Since we discussed it last time, I've been thinking about how Title IX could be applied without resorting to quotas (which I disagree with). It seems to me that it's all about equal spending of money (isn't it always). In fact, many departments already make up for the small number of women in their departments by spending extra money on women in general (e.g. sponsorship of Grace Hopper). Certainly, this could be taken into account.

But perhaps some of my disagreement with this article does stem from my disagreement with her argument. The final paragraph makes an argument I have made many times... for the other side:

American scientific excellence, though, is an invaluable and irreplaceable resource. The fields that will be most affected -- math, engineering, physics and computer science -- are vital to the economy and national defense. Is it wise, to say nothing of urgent, for the president and Congress to impose an untested, undebated gender parity policy at this time?

Yes.

Day of Silence

2009-04-17T10:43:00.002-04:00

About today:

The National Day of Silence brings attention to anti-LGBT name-calling, bullying and harassment in schools. Each year the event has grown, now with hundreds of thousands of students coming together to encourage schools and classmates to address the problem of anti-LGBT behavior.

Yet another reason to support action on this problem - 11 year old Carl Walker-Hoover killed himself on April 6th after anti-gay bullying in his school. Gay or not, anti-gay words are used to bully students in schools where they should be safe to learn. Teachers have the responsibility to do something about this. Please allow participating students to remain silent and consider speaking up yourself.

CS is King

2009-04-15T14:44:00.002-04:00

More bad news for business departments... more good news for us.

There are already signs of a renewed interest among students in science and technology. For the first time in six years, enrollment in computer science programs in the United States increased last year, according to a university survey last month. At Stanford University, the number of students taking the introductory computer science course increased 20 percent this year, said Eric Roberts, a professor of computer science.

(From: NYTimes article)

Ghana - A Summary In Photos

2009-04-13T21:01:00.018-04:00

Sunset over the Sahara on the plane to Accra.

A new mall in Accra, complete with a ShopRite and fancy cars. Neither were there the last time I visited six years ago.

The central library at the University of Ghana, Legon.

You can buy anything on the street.

An ad from the most recent presidential election.

The coast at Anomabo.

Cape Coast town.

A slave dungeon at Cape Coast Castle.

The new presidential palace. It's shaped like a stool - the traditional seat of power.

A tree that looks like a giant rohdedendron at Ashesi University College.

Going to Ghana

2009-03-20T16:12:00.000-04:00

I leave for Ghana today for two and a bit weeks. While it doesn't look like I'll have much interaction with OLPC Ghana, I do think I'll get to talk to some of the folks in computer science at Ashesi University, which should be interesting. I'm excited.

Highlights of my reading list while I'm there include:

Hot, Flat, and Crowded: Why We Need A Green Revolution - And How It Can Renew America by Thomas L. Friedman
Indexing Compressed Text by Paolo Ferragina and Giovanni Manzini

Perhaps if I brave the internet cafes I'll give some updates from the road...

It's About Time

2009-03-17T15:21:00.000-04:00

I never really understood why the dot-com bust led to such a drastic drop in computer science enrollments. It's always seemed rather short-sighted to me to ignore the drastic increase in the use of computers in, well, everything just because dot-coms weren't going to keep being such a big thing. But I suppose I underestimate the appeal of get-rich-quick schemes. Apparently the financial crisis has made banking so unappealing, combined with the desire to actually be able to find a job, that computer science is seeing a turn-around:

For the first time in six years, enrollment in computer science programs in the United States increased last year, according to an annual report that tracks trends in the academic discipline.

Hopefully this means that computer science faculty searches won't be cut with the budget.

On the other hand, while this may eventually change diversity trends, it hasn't yet: "the fraction of bachelor’s degrees awarded to women remained steady at 11.8 percent in 2008."

(See the NY Times article.)

Advisor Matchmaking

2009-03-16T16:04:00.003-04:00

Helping out with the grad admissions process at Maryland always makes me re-examine my department. This year, the theme to that re-examination seems to be the process of finding an advisor. At Maryland, for many people this process is self-directed. You think about what area you might want to do research in, take some classes, talk to some professors, and eventually ask one to be your advisor. I think part of the reason that some students have such trouble with this is that it's similar to asking someone out on a date - complete with all the anxiety that they'll say no, already have too many other dates, not want to commit to dating you for the next five years, etc. There are of course ways to ease into the advisor-advisee relationship (ways to have the first date without committing to marriage) - taking a class, doing an independent study, talking to them about their research, etc. Perhaps these can make the proposal less daunting, though I imagine that for the extremely shy, even doing these things is terrifying.

Still, I believe that this process is definitely better than the pre-arranged marriage. While the powers-that-be might assign you an advisor that you get along with and is in the area that you declared interest in when you entered grad school, you might instead end up with an advisor with a drastically different working style or change your mind about what you want to do. Even if you meet them once or twice before the marriage commences, it still bypasses the important courtship phase. Rushing the process does a disservice to all involved.

Barbara Liskov wins Turing Award!

2009-03-10T15:00:00.002-04:00

From the MIT announcement:

Institute Professor Barbara Liskov has won the Association for Computing Machinery's A.M. Turing Award, one of the highest honors in science and engineering, for her pioneering work in the design of computer programming languages. Liskov's achievements underpin virtually every modern computing-related convenience in people's daily lives.

Liskov, the first U.S. woman to earn a PhD in computer science, was recognized for helping make software more reliable, consistent and resistant to errors and hacking. She is only the second woman to receive the honor, which carries a $250,000 purse and is often described as the "Nobel Prize in computing."

The first woman was Fran Allen, who won in 2006. The award was first given in 1966. I find it hopeful that it seems that women are now being seriously considered.

(Via Michael and Suresh.)

A Fragile Peace

2009-03-09T10:30:00.003-04:00

I was in Northern Ireland a year ago. Victoria Square had just opened in Belfast. It's an open-air mall covered by a domed glass roof. From my point of view, it was beautiful and functional. Some older men I was talking to in a pub had something different to say about it, "it's just too tempting." It was a sign of prosperity and peace that something with that much glass was built in a city so used to bombings.

Yesterday, two British soldiers were killed northwest of Belfast. It's the first deadly attack on the British since before the Good Friday peace agreement. Both sides of the coalition government have denounced the attack.

Last year, N. Ireland was experiencing great prosperity. The consequences of peace were clearly visible. And there was hope. The US primaries were happening. The men at the pub also said, "if Obama, a black man, can become president of the United States, maybe there's hope for us here."

I'm hoping they're right.

Unperceived Bias

2009-03-03T14:59:00.002-05:00

A lot of the discussion (which I'm glad is still happening) that's been going on about double-blind reviewing has been making assumptions that we would know if there was bias (against women, unknown authors, whatever) and that part of the reason that this discussion is coming up is because these authors perceive this bias and are cranky about it. That is not my opinion. I've never perceived any bias and have no personal grievance against the process. In fact, the reviews that I've gotten have shown that the reviewers truly read and thought about my papers and took time to write thoughtful feedback. I deeply appreciate their efforts. The problem is that bias is often unperceived. I include my own biases in this, and work hard to recognize them in myself. Still, I believe that often bias is unconscious.

When I was taking an upper level math seminar in my sophomore year of college, there were two seniors in the small class who stood out clearly above the rest - one guy and one girl. When she presented her solutions to homework problems, it was as if we were hearing a guest lecturer. Every point was covered. Her presentation was organized. Her math was flawless. She was able to answer our questions precisely and in a way so that we could understand. The guy was a different story. It was clear that he didn't always do the work beforehand. Still, when he presented, after some staring into space and thinking on his feet, the correct solution would appear on the board. He explained it clearly and answered questions, sometimes finding - and fixing - flaws along the way. I realized one day, when talking to a friend about the class, that I considered him to be the more brilliant of the two, ascribing to her the "female" qualities of organization and assuming that her flawless performances were due to advance planning and not to her mathematical ability, while his successes were a sign of his brilliance. This assumption is sexist. I recognized my bias, my internalized sexism if you will, only after most of the semester had passed.

I will not believe you if you claim that you are never biased.

Getting Stuff Done

2009-02-28T14:35:00.004-05:00

I am a strong believer in discussion. Not just as a means to an end, but as important for itself. From that perspective, I think the discussion on double-blind reviewing was extremely productive (and I hope it will continue). I appreciated that comments were well-thought out and sincere, even if I didn't agree with them. But now I wonder, how do we take this discussion to a broader audience? As a first step, I'd be interested in getting more people within the theory community to be talking and thinking about these issues. Perhaps this is really a request to other bloggers to keep the conversation going.

More generally, how can we transfer conversations (online or in person) into action? Again, I wish to point out that often these conversations are important for themselves, still, sometimes once some amount of agreement is reached, the topics discussed merit action on a broader scale. Two examples, off the top of my head, of times when moving discussion to action has worked:

Yesterday, I spent some time standing in a hallway at Maryland talking to a fellow CS grad student. For awhile, I've been thinking in the back of my head about starting a thesis support group. I mentioned this to him and he was enthusiastic. We've organized the first meeting for this coming Friday and sent out announcements about it. Even if only the two of us show up, I consider this a success.
After tossing around the idea of holding a student-only conference event for SoCG (and it not happening), I posted about the possibility for future conferences. I got a positive response and it sounded at the time like it might actually happen for SoCG 2010. (Of course, I haven't been paying any attention to this in awhile, so I don't really know. Suresh?)

Both of these examples had the advantage of requiring little effort and a small number of people to be interested. What if that isn't true? Suppose we decided to try to continue the discussion of double-blind reviewing and possibly to try to start using it. How would that happen? A vote at the business meeting seems like a later step in the process. Discussion seems like the first step. What happens in the middle?

Double-Blind Reviewing

2009-02-18T17:59:00.002-05:00

Updated 2/22/09: Added problems 5-8 as I understand them from the comments. These are mostly just extensions of 1-4, but I'm trying to make that more clear.

Michael discussed conflict of interest issues last week (in relation to STOC PC discussions). For me, the discussion brought up the question of why we don't use double-blind reviewing, thus handling the bias issue that is at the heart of conflicts of interest in a way that's been shown to reduce bias. And I do mean shown, I'm not just guessing that it might reduce bias, it's been shown to reduce bias against female authors (I'm willing to extrapolate from that that it reduces bias in general). I know that many people are against using double-blind reviewing for theory conferences. I don't understand why. Here are my guesses about what objections might be, and the reasons that I don't agree with them or understand them.

I, the author, am too lazy to anonymize my paper
It doesn't really take any extra work to do basic anonymization of a paper. Most people refer to themselves in the third person when talking about their past work anyway. We don't have large continuing software projects, so we don't need to anonymize the names of those. These seem like the only real pieces of the paper that can reasonably be anonymized.
I, the PC member, am too lazy to deal with anonymized papers
Having never been a PC member, I don't understand this potential argument.
It wouldn't actually be possible, everyone would know who's paper it was anyway
Again, double-blind reviewing has been shown to reduce bias. As scientists, it seems that we should respect the research and not just decide that this would happen.
I, the author, want to be able to post a copy of my paper on my website as soon as I submit it.
This does seem like an issue that would need to be dealt with. In general, I don't think that most reviewers/PC members would actually go trying to find the paper they're reviewing to determine whose it is. Authors could be asked not to post information and/or reviewers could be asked not to look for it. I'm not convinced that the web-based version of this problem is significantly worse than the traditional version where colleagues know what each other are working on.
We're better/smarter than other fields and don't actually have a problem with bias affecting which papers we accept.
See #2 and #6. Also, without some sort of research to back this up, if you make this argument I'm likely to assume that you don't have the necessary social science background to accurately support this claim. (I certainly don't.)
The identity of the authors helps to determine if the paper will have an impact/ turn out in hindsight to have been good.
This is an argument I do understand and find logical, but I strongly disagree with it. I believe the work should stand on its own. Perhaps I should actually have phrased this problem as I, the reviewer, am too lazy to take the time to fully read and consider the paper. I think this raises some interesting issues about the quality of reviewing, and perhaps revisions to that process also should be considered. But I admit that I may be missing something here, having not reviewed a large number of papers. Still, I imagine that most of us would be wary of a conference that explicitly stated that it took the reputations of the authors into account. If we're not willing to explicitly state the rules by which we do this, we shouldn't do it at all (again, because it's obviously biased).
Our reactions to double-blind reviewing are based on emotions. Some people find it fair and rigorous. Some people find it insulting and limiting.
This also makes sense to me. I'm clearly in the first category, and don't understand the second. I believe it's a compliment to authors that their work can stand on its own, without having their name get the work through (see #6). I don't find it at all limiting (see #4 and #8).
If we can't do it perfectly, we shouldn't do it at all.
See #3 and #4. Of course there are always going to be reviewers who guess the authors (correctly or incorrectly). There might even be reviewers who are already familiar with the work because it was posted online already. In some ways, it becomes up to the authors to determine if the reviewers will know that it's their paper - those of us who are on the negative end of the bias spectrum or just believe in this process can choose to really be careful so that reviewers won't know it's our paper. But whatever happens, there will be some papers that actually remain anonymous and are judged only according to the work done. I'm fine with a system that's better even if it's not perfect. Similarly, I recognize that this won't suddenly fix all the problems women in computing face. It's still no reason not to fix this one.

In general, it seems to me like not too much work for a known reward.

(A nice overview of the issues can be found in an editorial in Nature.)

Free CG Journal?

2009-02-16T10:20:00.001-05:00

Dense outliers currently has a poll up about starting a free computational geometry journal. Go vote!

SoCG Accepted Papers

2009-02-12T15:04:00.004-05:00

The SoCG notifications just went out, and included a list of accepted papers. Sadly, there is only one paper on kinetic data, and though it looks interesting, it's not mine. Here's the list.

-----

Micha Sharir. An Improved Bound on the Number of Unit Area Triangles

Boris Bukh, Jiri Matousek and Gabriel Nivasch. Lower bounds for weak epsilon-nets and stair-convexity

Joachim Giesen, Balint Miklos, Mark Pauly and Camille Wormser. The Scale Axis Transform

Francis Y. L. Chin, Zeyu Guo and He Sun. Minimum Manhattan Network is NP-Complete

Eyal Ackerman, Jacob Fox, J\'anos Pach and Andrew Suk. On Grids in Topological Graphs

Mohammad Abam and Mark de Berg. Kinetic Spanners in R^d

Naoki Katoh and Shin-ichi Tanigawa. A Proof of the Molecular Conjecture

Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas Guibas and Steve Oudot. Proximity of Persistence Modules and their Diagrams

Mark de Berg, Herman Haverkort and Constantinos Tsirogiannis. Visibility Maps of Realistic Terrains have Linear Smoothed Complexity

Gaiane Panina and Ileana Streinu. Flattening single-vertex origami: the non-expansive case

Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Thomas Hackl, Bert Juettler, Margot Rabl and Elisabeth Pilgerstorfer. Divide-and-Conquer for Voronoi Diagrams Revisited

Marc Pouget, Sylvain Lazard, Elias Tsigaridas, Fabrice Rouillier, Luis Peñaranda and Jinsan Cheng. On the topology of planar algebraic curves

Sylvain Pion, Vicente H. F. Batista, David L. Millman and Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers

Pankaj Kumar Agarwal, Esther Ezra and Micha Sharir. Near-Linear Approximation Algorithms for Geometric Hitting Sets

Sandor Fekete, Dietmar Fey, Marcus Komann, Alexander Kroeller, Marc Reichenbach and Christiane Schmidt. Distributed Vision with Smart Pixels

Gunnar Carlsson, Vin de Silva and Dmitriy Morozov. Zigzag Persistent Homology and Real-valued Functions

Mikael Vejdemo-Johansson and Vin de Silva. Persistent cohomology and circular coordinates.

Andrea Vattani. k-means requires exponentially many iterations even in the plane

Natasa Jovanovic, Jan Korst, Ramon Clout, Verus Pronk and Ludo Tolhuizen. Candle in the Woods: Asymptotic Bounds on Minimum Blocking Sets

Bernard Chazelle and Wolfgang Mulzer. Computing Hereditary Convex Structures

Nabil Mustafa, Saurabh Ray, Abdul Basit and Sarfraz Raza. Centerpoints, Tverberg's Technique, and Related Problems

Nabil Mustafa and Saurabh Ray. PTAS for geometric hitting set problems via Local Search

Jean-Daniel Boissonnat, Olivier Devillers and Samuel Hornus. An efficient implementation of the Delaunay triangulation and it's graph in medium dimension

Sang Won Bae and Kyung-Yong Chwa. The Geodesic Farthest-Site Voronoi Diagram in a Polygonal Domain with Holes

Chuanjiang Luo, Jian Sun and Yusu Wang. Integral Estimation from Point Cloud in $\real^d$: a Geometric View

David Eppstein, Elena Mumford, Bettina Speckmann and Kevin Verbeek. Area-Universal Rectangular Layouts

Andrea Francke and Michael Hoffmann. Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard

rom pinchasi. Halving Lines and Measure Concentration in the Plane

Tamal Dey and Kuiyu Li. Cut Locus and Topology from Surface Point Data

Marc van Kreveld and Rodrigo Silveira. Embedding Rivers in Polyhedral Terrains

Mashhood Ishaque, Bettina Speckmann and Csaba Toth. Shooting permanent rays among disjoint polygons in the plane

Chandra Chekuri, Ken Clarkson and Sariel Har-Peled. On the Multi-Cover Problem in Geometric Settings

Timothy Chan and Sariel Har-Peled. Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

Bernd Gärtner and Martin Jaggi. Core-Sets for Polytope Distance

Kasturi Varadarajan. Epsilon Nets and Union Complexity

Timothy M. Chan and Eric Y. Chen. Optimal In-Place Algorithms for 3-d Convex Hulls and 2-d Segment Intersection

luc habert and michel pocchiola. Arrangements of double pseudolines

Friedrich Eisenbrand, Nicolai Haehnle and Thomas Rothvoss. Diameter of Polyhedra: Limits of Abstraction

Chee Yap and Long Lin. Parametrizability and Nonlocal Isotopy: An Approach to Efficient Approximation of Nonsingular Curves

Erin Chambers, Jeff Erickson and Amir Nayyeri. Minimum Cuts and Shortest Homologous Cycles

Don Sheehy and Gary Miller. Approximate Center Points with Proofs

Csaba Toth. Binary Plane Partitions for Disjoint Line Segments

Peyman Afshani, Chris Hamilton and Norbert Zeh. Cache-Oblivious Range Reporting With Optimal Queries Requires Superlinear Space

Glencora Borradaile, James Lee and Anastasios Sidiropoulos. Randomly removing g handles at once

Peyman Afshani, Chris Hamilton and Norbert Zeh. A Unified Approach for Cache-Oblivious Range Reporting and Approximate Range Counting

STOC accepted CG papers

2009-02-10T17:11:00.003-05:00

The list of STOC 2009 accepted papers was posted on Friday. Happily, they also provided an html version with abstracts. Below are the computational geometry related papers I noticed on the list (and then happily stole from the html source).

Small-size ε-Nets for Axis-Parallel Rectangles and Boxes

Boris Aronov, Esther Ezra and Micha Sharir

We show the existence of ε-nets of size O((1/ε) log log (1/ε)) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in 3-space and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size O((1/ε) log log log (1/ε)) for the "dual" range space of "fat" regions and planar point sets. Plugging our bounds into the technique of Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding (primal or dual) range spaces.

Private Coresets

Dan Feldman, Amos Fiat, Haim Kaplan and Kobbi Nissim

We forge a link between coresets, that have found use in a vast host of geometric settings, and differentially private databases that can answer any number of queries without compromising privacy — queries of the same class well approximated by the coreset. Such queries imply efficient privacy preserving optimization algorithms for a wide range of optimization problems but are also of independent interest. We give (computationally inefficient) transformations from any coreset for queries with low generalized sensitivity to differentially private databases for the same queries. This greatly extends the work of Blum, Ligett, and Roth [BLR08], and McSherry and Talwar [MT07].

We define the notion of private coresets, which are simultaneously both coresets and differentially private. We produce computationally efficient private coresets for k-median and k-mean in R^d, i.e., efficient differentially private databases for such queries. Private coresets also imply efficient coalition proof mechanisms and error resilient data structures.

Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have a (small) additive error.

Explicit construction of a small ε-net for linear threshold functions

Yuval Rabani and Amir Shpilka

We give explicit constructions of ε nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments.

As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c\sqrt{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c\sqrt{n}.

Every planar graph is the intersection graph of segments in the plane

Jeremie Chalopin and Daniel Goncalves

Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.

Jury Morality

2009-02-06T10:59:00.004-05:00

Not only was I chosen for jury duty, I was chosen for the jury. I was surprised by this, though I'm not sure why (perhaps since I was 39th in the queue). I suppose if they left a lawyer on the jury, I'm comparatively very little threat.

The deliberations were interesting, and the whole process left me wondering about the morality of the system. Because it appears that justice and morality are two very different things. Should they be? This was actually a major sticking point in our deliberations. We were deadlocked.

There's a classic psychology scenario (used, I believe, to understand through their answer what stage of moral reasoning a subject has reached) that goes something like this:

A man's wife is very very sick. Without a certain very expensive medicine she will die. The man does not have enough money for the medicine. Should he steal it?

My modifications to the scenario assume that he does steal the medicine (or, since he's innocent until proven guilty, is found with the medicine in his possession).

Should he be found guilty of the crime?
What if he first talked to the owner of the store, who refused to help him out, put him on a payment plan, etc? Is he still guilty if he steals it?
What if it turns out the owner of the store was actually an undercover cop who could have given him the medicine, but wanted to make an arrest?
What if the undercover cop says the guy stole the medicine while the man says the cop opened the door and told him it was "on the house?"

My take on this is that in only the fourth case is there cause for reasonable doubt. But I don't like it.

Jury Math

2009-01-28T17:33:00.006-05:00

For the first time ever, I got called for jury duty. Yet another place in which better use of computers would really expedite the process (did we really need to answer questions with our assigned number so that it could be written down by hand? Isn't there some automatic way to do this? Maybe involving answering questions in advance, all at once? Etc.). The jury selection process was the most interesting part. From what I could gather, the rules for the selection were as follows (after jurors were asked individual questions earlier):

Randomly order the potential jurors.
Fill the jury seats with the jurors at the front of the queue (for criminal trials, that's 12 jurors plus 2 alternates or 14 seats). Some jurors in the queue are skipped over at the discretion of the judge (presumably based on the earlier questions). The judge has no limit on the number of jurors they may skip over.
Each attorney is allowed 10 dismissals. These dismissals are done in rounds. In each round, each attorney may dismiss a juror or pass. I'm assuming that the attorneys don't try to dismiss the same juror. When jurors are dismissed, new jurors from the queue are inserted into the empty seats. I also assume that if an attorney passes "too many" times in a row then the judge gets annoyed and makes them choose.
When all 10 dismissals are made, the process is over and all remaining jurors are dismissed. The jury are the people left in the seats at the end of the process.

So then, the questions are: What's the optimal strategy for each attorney? What if the desirability of a juror is not independent of the other jurors chosen? Ignoring the random ordering, what's the best position for a potential juror (assuming that they don't want to be chosen and assuming that they can't chose to be near the end of the queue) - how much do the surrounding jurors matter? How does this change if attorneys are allowed an unlimited number of dismissals, but have to pull the jury from the limited queue?

This is how I entertained myself while waiting. Well, that and thinking about how the white noise switch that the judge used when the attorneys were talking at the bench and we weren't supposed to hear them was sort of cool. Really the only mildly high-tech piece of the whole experience.

Inauguration!

2009-01-21T16:41:00.015-05:00

I was at the national mall yesterday for the inauguration. It was crowded and amazing. I made it there without too much trouble, including awhile spent on a metro platform trying to get out of the station with thousands of other people, singing "Na Na Hey Hey Kiss Him Goodbye." I ended up just about as close as I could have, considering that I didn't have a ticket. I was in that fourth clump back from the capitol reflecting pool, just past 7th street. And I could see one of the jumbotrons pretty well. The inauguration was moving and of course historic, but I think the most touching thing was the turnout and the joy among those of us watching, happily shoved up against each other. We were a happy mob - peacefully jumping over fences to get into the inauguration or chanting "move that bus" as we tried to leave en mass. I'm glad I went.

I also went on Sunday to the concert at the Lincoln Memorial. It was, if possible, more moving than the inauguration. There's just something about a giant crowd singing "This Land Is Your Land" while swaying and meeting each other. And since it was longer, there was more time to set the history of the moment through presidential quotes, famous singers, and shots of the memorial itself. They also showed clips of past important meetings at the memorial - Marian Anderson and the MLK March on Washington.

There were about 750,000 people on Sunday and about 1.8 million yesterday, making yesterday the largest gathering ever on the national mall. And some people were turned away (though it looks from the satellite photo like there was room, I believe it was all fenced off). The police, army, national guard, metro police, etc. were visible, but not always so good at directing people to the right route. Still, I think the city did a good job, considering. I wonder if understanding the Natural Algorithms that caused the crowd to create those clusters would help in the future.

My city has been celebrating in a unified, gleeful way. And now I'm excited to see what President Obama will do. And excited in general every time he's called "President Obama."

Passed!

2009-01-14T20:25:00.002-05:00

For the past week I've been frantically making intricate animations for the talk for my proposal (this is the problem with doing work on moving points - if you know of any good software, please leave a comment). The proposal was today, and I passed! It's strangely anticlimactic, since it's really a mid-process deadline, but exciting nonetheless.

SODA 09

2009-01-07T10:25:00.004-05:00

I got back from SODA last night amidst the snow (NYC) and rain (DC). I suspect that somewhere in the middle it was ice, so I hope the folks that were driving made it home safely.

Chazelle's talk on "Natural Algorithms" was a highlight. I also have no desire to focus on minute changes in run times, so I enjoy the talks that introduce new problems the most. By that measure, Chazelle's talk was especially good. He discussed the convergence time of a flock of birds, but more generally introduced (or probably re-introduced) the idea of examining natural phenomena through an algorithmic lens. One of the problems I've been thinking about also involves bird flight - can we calculate the migratory path of birds in an online manner as they fly? I suspect that looking at it from the birds' perspective instead of an all-seeing perspective would also be interesting. So perhaps my enjoyment of the talk was really because it related to my work, but I'd say that it related to many problems and that's what made it good. (Of course, he's an excellent speaker... his talk on "How to Win the Best Paper Award" was given at the business meeting.)

I also enjoyed the talk and paper by Yi and Zhang, "Multi-Dimensional Online Tracking." The talk was scheduled right after lunch on the last day, so if you missed it, that might be why. They considered the problem of online maintenance of an approximate value for a changing function. Again, it's related to my work so I'm biased, but I appreciated the problem and thought the 1D solution was especially clean. It's worth a read, or at least a skim.

The proceedings this year were distributed on a CD instead of printed. Abstractly, I think this is a great idea, since after the conference I would be unlikely to look at the hard copy of the proceedings... but I missed them during the conference. Still, if they're keeping the proceedings online and free permanently, it's a net win.

Overall, it was an enjoyable conference. It was good to see/meet some of you. I'm sad to return to "the real world" in which I have a lot of work to catch up on...

Another for the Map Archive

2008-12-29T15:36:00.003-05:00

An interesting prediction. Clearly the most suspect part of his prediction is that the boundaries would be along state lines. Oh, and that Kentucky and Tennessee would be grouped with the northeast. And well, really, all of it.

Women in Computer Science Worldwide

2008-12-19T10:04:00.009-05:00

Updated 12/24/08: I've updated the map to reflect the anecdotal and cited information from the comments. Also, I changed the coloring scheme to be one from ColorBrewer, so hopefully the distinctions are clearer. Thanks all!

Percentage of Computer Science Undergraduates that are Women
Dark blue: < 15% Medium blue: 15% to 30% Light blue: 30% to 45% Purple: 45% to 55%

D. Eppstein pointed out, as a comment to the previous post on sex vs. gender, that the percentage of women in computer science varies greatly by country, and that "any argument that the correlation between gender and CS skill is sex-based would have to take account of that." I've heard lots of anecdotal evidence that this is true, but was curious about the numbers. The most comprehensive resource I could find was a summary of women in computer science by country from the Anita Borg Institute. Sadly, it was rather brief and didn't have the same information about each country (understandably). I took the information from that file to make the map above based on the percentage of women undergraduates in computer science (or math/computer science, or whatever the file had info on). I'm sure that information exists for many more countries than I've labelled, and I'd love to know what it is. If you know, please leave a comment with your source and I'll add it to the map.

Sex vs. Gender

2008-12-16T11:52:00.003-05:00

Recently I've been thinking a lot about the difference between sex and gender. And it makes me wonder, "is this one of the subtleties that causes confusion about the women in cs issue?" But first, I suppose I should explain what I see as the difference between the two words/ideas, which understandably cause much confusion and are frequently used in the definition of each other. Sex is the biological condition of being male or female. (Already this is more complicated than I'm saying, since of course there are people who don't fix nicely into those categories based on their bodies or their chromosomes.) Gender refers to the set of characteristics that are associated with sex groups. So, "liking dolls" is a quality that is thought of as being gendered female. It does NOT mean that all women like dolls, or that all doll-liking people are all women. I like to think of it as a statistical correlation. And it does not and should not imply causation. Being a woman does not cause you to like dolls. (Believe me.)

And this is where Larry Summers went wrong. (You knew I'd get to him eventually.) He looked at the low numbers of women in the sciences and decided that it must imply that women (sex) do not have the intrinsic aptitude for the field. In other words, the smaller number of men who like dolls (or admit it) implies that men can't like dolls. They just don't have the intrinsic ability to like dolls (or the color pink, or cooking, or English literature, or...). Which is obviously ridiculous. Computer science is currently gendered male. There's a (strong) statistical correlation between being in computer science and being male. But gender is a socially constructed concept. So don't tell me that women (sex) just aren't as good at computer science as men or pretend that the current gendered norm means anything about a more permanent biological state.

A Better Reality

2008-12-12T09:37:00.004-05:00

There's a new ad out about clean coal, and it makes me happy every time I see it. The ad consists mostly of a guy who says he's showing you around a clean coal plant, but he's standing in the middle of an empty field. Because of course, there's no such thing as clean coal. To paraphrase the TV show The West Wing, clean coal is just something that pollsters came up with because it sounds better than regular coal. Yet it was all over the presidential debates from both candidates. But hopefully now that the election is over this problem can actually be examined.

Perhaps it'll be examined by the new energy secretary, Physics Nobel laureate Steven Chu. It's thrilling that there will be smart people in office who are actually interested in doing something about climate change. (A nice NY Times blog post about Chu.)

Day Without a Gay

2008-12-09T14:54:00.002-05:00

Continuing the Join the Impact campaign against California's Prop. 8 and for gay marriage and gay rights, tomorrow is Day Without a Gay*. The organizers urge everyone, not just gay people, to "call in gay" to work and instead donate your time to local service organizations in need of volunteers. They also suggest not consuming for a day. The goal is visibility for gay issues. As I've mentioned earlier, it's part of a larger movement which frames these issues in terms of civil rights.

I'll be participating, though I admit it feels rather like it won't have a big impact. After all, it'll just be another day when I don't go to campus and stay at home to work. Though I will be avoiding my neighborhood coffee shop at which I have "regular" status.

* Here, "gay" is being used as an umbrella term. In fact, that's usually the way I use it. If you prefer, whenever I say "gay" you can replace it in your head with "LGBTQ" or "queer" (for the more social theory academically minded among you).

Adjuncts, Adjuncts Everywhere

2008-12-03T10:29:00.008-05:00

A report was released today by the American Federation of Teachers (see also the Inside Higher Ed article) which details the large numbers of adjunct teachers who now teach a large percentage of courses at all types of colleges in all disciplines. (Note that this includes graduate students who have full control for a class, but does not include TAs in classes run by a tenure-track faculty member.)

Across public colleges and universities, the report finds that full-time, tenured or tenure-track faculty members make up only 41 percent of instructional staff, while full-time non-tenure-track make up 20 percent, part-time faculty members off the tenure track make up 20 percent, and graduate employees are another 19 percent.

This has been flying under the radar for awhile now, and I'm glad that it's getting some press due to this report. It's clearly a problem for students and faculty alike, yet I doubt that this trend will change anytime soon, especially given the economy.

The Inside Higher Ed article also gives a table showing the breakdown by discipline. Computer Science/Engineering fares well - we have some of the lowest numbers of contingent instructors. In fact, the numbers seem to mirror the discipline gender breakdowns I discussed recently, with "male" disciplines having lower numbers of contingent instructors. My guess is that this is due to money - "male" disciplines are more highly valued -> get more money -> can afford to hire tenure-track faculty -> have fewer contingent instructors. So, for example, 54% of undergraduate courses in Human services at research universities are taught by contingent instructors while in Engineering/Computer Science that number is 29.6%.

More to the point, at 29.6% it's amazing we're at the low end of the spectrum. The high end is for undergraduate Education classes at community colleges - 77% of classes are taught by contingent instructors. I can only imagine what a mess that creates of department community and resources.

Join the Impact

2008-11-26T12:07:00.003-05:00

A few weeks ago (Saturday, Nov 15th) was the Join the Impact protest against California's Prop 8 which removed the right that gay people had previously held to marry. Simultaneous protests happened across the country. I went to the one in DC and we marched from the capitol building past the Washington monument (or as one of the protest organizers called it, the national phallic symbol) to the White House. There were somewhere between 5 and 10 thousand people there, despite the tornado warning and heavy rain. It was a wonderful protest and the start of what I think will be an exciting movement.

One of my friends from college was the organizer of the DC protest and Pam's House Blend has a nice interview with him.

Go to Join the Impact for information about future events.