Monday, November 1, 2010

Teacher Tenure

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.

Tuesday, October 26, 2010

The Teacher Myth

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?

Friday, October 22, 2010

Superman's Statistics

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.

Tuesday, October 5, 2010

Water in a Cube

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

Wednesday, September 15, 2010

ESA 2010

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.

Tuesday, August 24, 2010


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.

Monday, July 12, 2010

Theorists Getting Jobs

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.

Thursday, July 1, 2010

Top Three Pieces of Advice

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.

  1. 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
  2. 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
  3. 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.

Tuesday, June 29, 2010

You Must Be Really Smart

(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.

Sunday, June 27, 2010

Women in Theory

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:

  1. Leaving out half of the world's work force isn't the best strategy for good scientific progress.
  2. 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.
  3. 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.)
  4. 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!

Saturday, June 19, 2010

SoCG, Day 3 and MASSIVE

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.

Wednesday, June 16, 2010

SoCG, Day 2

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...

Monday, June 14, 2010

SoCG, Day 1

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!

Tuesday, June 8, 2010

Range Searching Over Compressed Kinetic Data

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.

Thursday, June 3, 2010

Women: Objects Unable to Survive Without Telephones

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.

Tuesday, May 25, 2010

Packing Rectangles

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?

Wednesday, May 19, 2010


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.

Wednesday, May 12, 2010


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.

Thursday, April 15, 2010


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 "" with "" 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...

Wednesday, April 14, 2010


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.

Tuesday, April 13, 2010

Sensor Data Sets

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.

Monday, April 12, 2010


The ESA 2010 deadline is tonight at midnight Honolulu time.

The MASSIVE 2010 deadline is Wednesday.

Friday, March 19, 2010

Science Skeptics

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.

Thursday, March 11, 2010

Sophie Morel

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.

Monday, March 8, 2010

Women in Science Overview

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.)

Thursday, February 25, 2010

Job Searching Comrades

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.

Tuesday, February 16, 2010

SoCG 2010 Accepted Papers - Motion

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