price.mit.edu/blog

Archive for the ‘computer science’ tag

Unlocking the Clubhouse, part 1: it’s not about innate differences

leave a comment

If you work on computing in school, on the side, or in industry and you’ve been paying attention to the people around you, you’ve probably wondered why so many fewer women than men enter our field and stay in it.

This is no immutable law. In fact, the proportion of women in computer science in the United States was once much higher. Of people receiving bachelor’s degrees in computer science, women made up nearly 40% in the mid-1980s, declining to 20% in 2006. (graphs, NSF data.) And it varies among cultures, too—in Malaysia, women actually outnumber men in computer science. (data, analysis)

So the natural way to ask the question is in this form: What are we doing in computer science that causes so many fewer women than men to enter our field and to stay in it? And what can we do differently to change that?

Recently I picked up a book on this subject. Unlocking the Clubhouse is the product of a collaboration between Jane Margolis, a social scientist studying gender and education, and Allan Fisher, the founding dean of the undergraduate program in computer science at Carnegie Mellon University.

The authors gather scores of previous studies, and they did their own work from a privileged position at the helm of the undergraduate program at Carnegie Mellon University. Their success at answering these questions may be indicated by the reversal they achieved of national trends at CMU in the five years of their research:

  • Before the authors’ work, the proportion of women among entering freshmen ranged from 5% to 7% over the five years 1991-1995. At the conclusion of their project in 2000, this proportion had reached 42%.
  • Graph of percentage of women in computer science freshman class at CMU, 1989-2000

  • Of students entering the program at the start of the project in 1995, only 42% of women remained after two years. This rate rose to 80% for women entering in 1996, and stabilized at nearly 90%. The rate among men was steady around 90%.
  • Graph of persistence rate for women and men in undergraduate computer science at CMU, 1995-1998

With that kind of success in practice, it’s clear their scientific findings and their recommendations have earned serious consideration. In a future post I’ll say more about those, and I’ll also look at what some other people have found on the subject. Ironically, it turns out one result of Margolis and Fisher’s success may have been to invalidate some of their findings in the new environment they created.

Written by Greg Price

February 15th, 2010 at 1:59 am

Math is hard

leave a comment

This week I got myself eaten by a math problem. Fortunately the problem is solved now, and I’ve escaped. Let me explain.

Two years ago, I was in Erik Demaine’s class about computational geometry, and heard about a problem that I wanted to solve. Suppose you have a convex polyhedron in ordinary 3-space. Then there is an intrinsic metric on the surface points of the polyhedron: the distance between two points is the length of the shortest path between them that runs along the surface. You can describe this metric to me without mentioning the embedding in 3-space, for instance by giving the shapes of a bunch of triangles and telling me which sides connect to which. The metric will certainly have these three properties:

  1. it’s homeomorphic to a 2-sphere: I can put the triangles all on a sphere preserving their interconnections, if I’m willing to stretch and bend them
  2. it’s a polyhedral metric: every point has a neighborhood with the same metric as a Euclidean disk (for most points) or cone (for the vertices)
  3. it’s locally convex: every circle of radius r has circumference at most 2πr

Now suppose you hand me a metric in the form of a bunch of triangles and notes on which edges to connect to which, and I confirm that they satisfy properties 1, 2, and 3. The great thing is that this is actually enough to guarantee that the triangles can be put together in 3-space to form some convex polyhedron, and this polyhedron is unique. (Here it’s crucial that I be allowed to bend the triangles, but without stretching — like paper.) Soviet mathematician A. D. Alexandrov proved this theorem in the 1940s. But Alexandrov’s proof doesn’t say how I can actually go and construct this embedding, so it opens up an algorithmic problem: given a metric satisfying properties 1, 2, and 3, how can we construct the unique convex polyhedron with this metric that Alexandrov’s theorem guarantees us?

Just the previous year, mathematicians Alexander Bobenko and Ivan Izmestiev had shown how to build the polyhedron by solving a rather involved differential equation. I figured it should be possible to get an explicit algorithm by discretizing their differential equation, and put a time bound on it by showing that the discrete steps don’t have to be too small. I cornered math problem-solver extraordinaire Daniel Kane, we sat down for a couple of hours with the Bobenko-Izmestiev paper, and he agreed—this shouldn’t be too hard.

Well, we were half right. Our approach worked, and we obtained an algorithm with an explicit time bound, a polynomial in the size of the input and its geometric ratios. Voilà:

Theorem. Given a convex polyhedral metric M homeomorphic to a sphere with n vertices, ratio S between the largest and smallest distance between vertices, and defect (discrete Gaussian curvature) between ε1 and 2π−ε8 at each vertex, an ε6-accurate ε9-convex embedding of M can be found in time

Õ(n915/2 S832 / (ε121 ε1445 ε8617) )

where ε = min(ε6/nS, ε9 ε12/nS6).

Now, that bound with its enormous exponents was great for getting people’s attention in talks. You don’t often see a time bound like that, and the reason is that to get that bound we had to pursue the problem and hammer it out piece by piece, assembling a diverse array of geometric lemmas, long past the point where sane people might have stopped. Daniel and I probably spent close to 100 hours meeting and working on the problem, some of it together with Erik, and I spent something like two or three times as long nailing all the details down in writing. The work became my master’s thesis, I presented it at the WADS conference this summer, and we submitted the paper to a journal. We breathed easy for a while.

Then we heard back from the reviewers. Turns out peer review is a good idea. One reviewer grabbed onto a particular subproblem that he apparently thought was more interesting than the whole rest of the paper. At each iteration we need to find an appropriate retriangulation of the surface. What we need is described by a well-understood concept, a “weighted Delaunay triangulation“. In the familiar Euclidean setting a Delaunay triangulation is equivalent to a “Voronoi diagram“, so we originally thought that some existing papers that described how to compute a Voronoi diagram on a polyhedral surface were enough to give us the weighted Delaunay triangulation we needed.

This reviewer demanded we give more attention to the issue, and he was right—the problem was harder than we realized. On a polyhedral surface things are more complicated than in the plane; for one thing, there can be infinitely many straight lines between two points, and to make a Delaunay triangulation you need to use the right ones. But in two marathon sessions this week and 2000 words of writing, Daniel and I worked out how to get an unweighted Delaunay triangulation from a Voronoi diagram, and then how to adjust the triangulation to handle weights. So the reviewer was right to think the problem more interesting than we had treated it, and now we’ve solved it. Since our new algorithm for Delaunay triangulation is straightforward and is known to run in a practical amount of time, it may prove to be the most reusable part of the paper.

Anyone interested can read more in the paper (pdf). The new Delaunay triangulation algorithm is in the last section.

So that was my vacation. How was yours?

Written by Greg Price

January 4th, 2010 at 1:32 am

Posted in Uncategorized

Tagged with , ,