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.