## 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.
http://intractability.princeton.edu/blog/2009/11/women-in-theory-2010-workshop/
The format will be similar to the WIT 2008 workshop. You can view information on that workshop at:
http://www.cs.princeton.edu/theory/index.php/Main/WIT08
and view a video of WIT08.

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

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

## 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: http://conferences.proboards.com/.

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

## 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:

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

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

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

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

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

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

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

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

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

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

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

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

## 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 Google.org, was excellent. She showed us a map of the world highlighted based on the number of search queries from the region (I wish I could find the map, it was definitely worth seeing). Africa was mostly empty of queries in comparison to the rest of the world. One of the things I really appreciated about her description of ways to change that was her acknowledgement that the people of Africa are highly intelligent and will "bring the internet to themselves."

• I went to a talk about feminism and technology. The highlight was a Skype'd in call from a woman in Pakistan. She discussed how technology is increasing women's freedom to work, even if they aren't allowed to leave their homes. It was amazing to see her, and the room was packed.
• The Best Practices in Introductory Computer Science Classes talk had some excellent and exciting ideas. My favorite suggestion (or really, theme) was the idea of taking projects that local community organizations need done, and giving them as class or group projects to the students. This motivates the students to do their best, since people are actually relying on what they get done, and also helps local organizations that frequently need small programs written but don't have the money to hire a programmer. While this might not work in an algorithms class, it seems like a good fit for a second or third programming focussed class.
• I stayed for the weekend after Grace Hopper to go hiking and get to see more of Tucson than just the hotel. I went with a friend who I met at the CRA-W Grad Cohort my first year of grad school. We're still friends and both still in grad school, so for a sample size of two Grad Cohort has been effective. We spent Saturday hiking in the desert, and Sunday exploring the surrounding mountains. Saturday evening we went to watch the sunset in a location suggested by one of the rangers, and were treated to a beautiful sunset, full moon, and group of people singing the sun to sleep. Apparently Tucson doesn't frequently have clouds, but that certainly wasn't my experience.

• Of course, no trip to Tucson is complete without cacti.

All in all, an excellent trip.

## Thursday, September 24, 2009

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 23, 2009

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

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

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 ### WADS 2009 Accepted Papers WADS 2009 accepted papers are now up. Sadly, no abstracts included. ## 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? Yes. ## 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

### Free CG Journal?

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

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