Wednesday, December 16, 2009

Second Women in Theory Workshop

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:
The format will be similar to the WIT 2008 workshop. You can view information on that workshop at:
and view a video of WIT08.

Sunday, December 13, 2009

Drugs - Less Scary Than Science

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.

Thursday, December 10, 2009

National Computer Science Education Week

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

Wednesday, December 2, 2009

Friday, November 20, 2009

Is DC Mature?

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.

Monday, November 16, 2009

FWCG '09 and the CRA-W/CDC Workshop

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.

Wednesday, October 28, 2009

Clustering Over Space and Time

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

Monday, October 26, 2009

National Computer Science Education Week

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.

Wednesday, October 21, 2009

Conference Roommate Finding Forum

Announcing a conference roommate finding board:

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!

Monday, October 19, 2009

On the Job Market

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

Friday, October 9, 2009

SoCG 2010 Call for Papers

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:

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

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)


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.

Tuesday, October 6, 2009

Grace Hopper 2009

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

Thursday, September 24, 2009

LATIN deadline

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.

Wednesday, September 16, 2009

Group Work

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:

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

Friday, September 11, 2009

New (Woman in Theory) Blog!

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

Friday, September 4, 2009

SODA accepted papers list

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.

Wednesday, September 2, 2009

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

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

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

Monday, August 17, 2009

Recommendation Letters

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.

Monday, August 10, 2009

Numb3rs Algorithm Clips

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.

Tuesday, August 4, 2009

Purple With Glee

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

Monday, July 27, 2009

Who Cares If They Learn?

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.

Monday, July 20, 2009

Happy Moon Landing

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

Monday, June 29, 2009

A Sensor-Based Framework for Kinetic Data

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.

Friday, June 19, 2009

At The Lake

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.

Monday, June 8, 2009

Life Is Unfair - Sue

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

Wednesday, June 3, 2009

The Cost of Being a Woman in CS

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.

Tuesday, June 2, 2009


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.

Tuesday, May 26, 2009

Sotomayor Nominated

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.

Thursday, May 21, 2009

Interactive Teaching

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

Tuesday, May 19, 2009

Not Happy to be Right

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?

Wednesday, May 13, 2009

Outrage, the movie

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.

Monday, May 11, 2009

Women Bully. And?

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.

Thursday, May 7, 2009


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.

Wednesday, May 6, 2009

SODA Call for Papers

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.

Tuesday, May 5, 2009

... And It Continues

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.

Thursday, April 30, 2009

Good Surprises

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:

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

Thursday, April 23, 2009

Tuesday, April 21, 2009

Continued Title IX Confusion

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?


Friday, April 17, 2009

Day of Silence

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.

Wednesday, April 15, 2009

CS is King

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)

Monday, April 13, 2009

Ghana - A Summary In Photos

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.

Friday, March 20, 2009

Going to Ghana

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:

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

Tuesday, March 17, 2009

It's About Time

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

Monday, March 16, 2009

Advisor Matchmaking

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.

Tuesday, March 10, 2009

Barbara Liskov wins Turing Award!

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

Monday, March 9, 2009

A Fragile Peace

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.

Tuesday, March 3, 2009

Unperceived Bias

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.

Saturday, February 28, 2009

Getting Stuff Done

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:

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

Wednesday, February 18, 2009

Double-Blind Reviewing

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.)
  6. 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).
  7. 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).
  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.)

Monday, February 16, 2009

Thursday, February 12, 2009

SoCG Accepted Papers

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

Tuesday, February 10, 2009

STOC accepted CG papers

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