Tag Archives: tcs

What does arXiving mean?

What does it mean to post a paper to arXiv?  More specifically, a paper that has not been accepted to a peer-reviewed venue; less specifically, to any easily-searchable, time-stamped, respected depository.

Scenario A: You have a result, but there is no decent deadline for another few months.  Maybe you know that a ‘competing’ team is working on the same result.  Should you post to arXiv?  Would that actually protect you from being scooped if someone else published the result in the meantime (perhaps at a venue that you deemed unsuitable)?

Scenario B: You are building on result B that has appeared in arXiv, but has not been accepted (yet?) at a peer-reviewed venue.  You have verified the work in B.  Can you reference an un-traditionally-published work?

Scenario C: You are reviewing a paper C and, being a diligent reviewer, you brush up on the latest in the area.  You find a very relevant paper posted on arXiv, paper X, dated before paper C would have been submitted.  Paper C makes no reference to paper X.  What do you do if: Paper C seems awfully similar (similar techniques, similar results) to paper X? Does your opinion change if Paper C is a subset or superset of paper X?
I suppose as a reviewer, you would review the paper and point out paper X to the editor/PC member.  But as an editor/PC member, what do you do?  After all, it is possible for independent researchers to come up with the same result using similar techniques at the same time (I have seen this happen).

What does arXiving mean?  Does it do more than provide an easy repository for papers?  Do we (in TCS) treat arXiv differently than other areas?

Writing reference letters

I was just sitting down to write the first1 reference letter that I have ever written and realized that I have never read a reference letter and have little idea of what should go into one.  This particular letter is for a graduate student applying for a fellowship.  Short post, but any suggestions?

Maybe I should start tweeting.

1 This is actually the third reference letter I’ve written, but the first was to be read by a close friend in the math department and the second was to be read by me.

A skulk of FOCS talks

The FOCS talks are now available online!  I waited until now to report on FOCS for this very reason.  I am not about to compete with Suresh or Lance for live blogging conferences.  I’m not sure where they find the time amidst talks and meetings in hallways to do so.  (I have to say, whenever I can’t make it to a conference, I very much appreciate such posts.)  I did manage to find the time to circle a few listings in my wonderfully compact one-page program as a reminder that I liked these talks and to point my students to them.  Of course, now I’ve forgotten why I liked them, but I can almost certainly guarantee that I was kept engaged throughout the talk and learnt something – a vote of confidence if I ever heard it!

In no particularly order (unfortunately it is not possible to link directly to the talk, so you’ll have to go and find them in the list):

  • The geometry of scheduling presented by Nikhil Bansal.
    Coauthored with Kirk Pruhs. I added the ever-so-wonderful note to my program: ‘neat not tight geometry problem’.
  • Fast approximation algorithms for cut-based graph problems presented by Alexander Madry
    I probably enjoyed the fact that Alex did not stand at the podium but walked around, indicating things on the slide (novel!).  Unfortunately the camera does not move from the podium.  Ghost speaker!
  • Approximating maximum weight matching in near-linear time presented by Seth Pettie
    Coauthored with his student, Ran Duan.  I’ve always enjoyed and always learned something from Seth’s talks.  I wonder if we could have a rating system for speakers with little stars in the program so that you can attend talks well outside your comfort zone if you know the speaker will be good?
  • A separator theorem in minor-closed classes presented by Ken-ichi Kawarabayashi.
    Coauthored with Bruce Reed. This talk had an amazingly thorough introduction that perhaps those new to H-minor-free graphs might appreciate
  • Logspace versions of the theorems of Bodlaender and Courcells by Michael Eberfield.
    Coauthored with Andreas Jakoby and Till Tantau.  I love the example tree decomposition and his slides more generally.  I keep meaning to ask him for his slides to get that tree decomposition figure …
  • A nonlinear lower bound for planar epsilon-nets by Noga Alon.
    Some of the best humour at the conference.
  • And of course Dan Spielman’s Nevanlinna-Prize talk Laplacian Gems. I have heard that his prize talk at ICM was amazing too, but I haven’t watched it yet.

So there’s three hours of fun theory listening for you.  I think they would pair well with a fine bottle of Oregon Gewurztraminer.

Women are not at an advantage in our field

I was asked a question a few months ago:

Do women have an advantage in our field?

There was a time when I would have chirped ‘NO!’ and stormed off.  That time might not have been too long ago.  But it is an interesting question, perhaps because it is so ill-defined.  What does advantage mean?  Which women?  Undergrads, grad students, faculty?  What is our field?  Computer science in academia, research labs, industry; theoretical computer science?

The arguments I have heard for ‘yes’ are all closely related.  Because you are a minority, you stick out and garner more attention.  Because we have all been told that we have to do something about the gender inequality, we go out of our way to make sure you are taken care of.  Because the higher-ups tell us that we need to improve our 10% rate, we have affirmative action policies so that we hire you.  I wish I’d done a better job over the years of keeping track of the various studies pointing to increased attrition rates for women at every stage of educational and professional advancement, women being judged based on their accomplishments and men on their potential, women needing to perform at a much higher level to reach the equivalent level as their male counterparts.  But I haven’t kept the links around; they can’t be that hard to track down, but I’m on a shuttle at the moment.  Instead I’ll give you my personal view.  The view I usually give when I am asked this question in person.

First, not all attention is good attention.  I do believe that when I meet someone at a conference that they are more likely to remember my name than I am to remember theirs.  Women do stick out when they are only a tenth of the population.  But often enough I have had the experience that I am not sought out for research conversation but because I am a woman.  Not because I am a computer scientist.*  Even though this may have only happened a handful of times in countless interactions, it makes me question whether all the truly professional interactions have really been so.  It makes me wonder: does this person even respect me as a computer scientist?  When/if it comes time for tenure letters, do I have to blacklist people who I feel see me first as a woman and then as a computer scientist?

At Waterloo, an undergrad told me that she was tired of all this “women in math” stuff she was expected to do.  She just wanted to study math.  So yes, sometimes the extra effort isn’t always positive.  At the training level, this extra effort can be viewed as unfair and undeserved attention that puts women at an advantage over men.  This perception itself lessens the advantage.

And then there is affirmative action.  A comment from a fellow grad student at Brown: “Well, you don’t have to worry, women have a much easier time getting jobs in our field [because of affirmative action]”.  Again, the misperception.  The intent of affirmative action is to overcome the (possibly subconscious) gender biases that are known to occur in the hiring process.  It is/should not the preferential hiring of candidates who are not competitive.  So long as we still hear comments like “she only got the job because she was a woman”, woman are not at an advantage.  And if you think this doesn’t happen, you just need to read the comment thread on the who got jobs where post over at Computational Complexity.

So, it’s my personal belief that woman are not at an advantage while training or working in academia.  I can’t speak for industry, but I can’t imagine it is much different.

* Yes, I realize that this is a two-way street, but I would argue that the gender inequality causes it to happen more often to women than men.

Experiments in teaching: problem-solving sessions

In a more significant experiment than the am-I-ready-for-this quiz, I am rethinking the assignments that accompany my grad algorithms course.  In last year’s class, I had the grad students work in randomly-assigned and rotating (different for each assignment) groups.  I will comment on this in another post.

I’m sticking with the group-based approach – partly for feasibility.  But rather than having standard written submissions and written comments/grades, I am having the students participate in a type of problem-solving session; and idea I stole from Claire Mathieu.

Each group will prepare solutions to some (2) problems ahead of the 2-hour problem-solving session.  Each group (A) will explain the solution to one of their problems X (picked by me) to another group (B) who will then explain the solution to me, with instant feedback/help/cleaning. Group B should leave the session satisfied that they understand the solution to X and will prepare a written solution within 2 days.  The grade of both group A and B will depend on the oral explanation I was given and the written solution to problem X.  Every group will take the role of teacher/student for one problem (that is, group B will then explain the solution to one of their problems, Y, to group A).  The written solutions will be placed into a (private-to-OSU) repository for other groups to see.  For details, see here.

Students are encouraged to repeat this process for other problems that they did not solve or learn; there are as many problems as groups (12) and every student knows who has solved each problem.  I’m hoping this will be a helpful, less lonely, way for them to prepare for the midterm and final (which will determine the bulk of their grade).

I’m hoping that this will help students learn to solve the types of problems they will be asked on the midterm and exam, and (more importantly) that they might face in their research (or in job interviews).  I’m also hoping that it is a more effective use of class time than hearing me lecture for another 2 hours a week. (I have 4 total hours per week of class time).

As before, I will (bravely) ask my students to comment.  I will try and do my best to take the comments into consideration to improve the remaining 5 problem solving sessions.  I have already received one comment that will take effect next session: in the last session, some problems went undiscussed; in future sessions, every problem will be discussed (by some pair of groups) and posted to the repository.  Comments from non-students are always appreciated!

Experiments in teaching: am-I-ready-for-this? quiz outcome

Last week, I gave the students in my grad algorithms class an am-I-ready-for-this? quiz.  I promised to report back, and I’m already a little late on that.  The average for the quiz was ~ 70% – I was hoping for a higher average, given how easy the quiz was (in my opinion).  Two students did not take the quiz (and have dropped the class) and two students (who were in the bottom 10%) did drop the class; so perhaps the quiz had the intended effect.

I am more interested in hearing what the students in my class have to say, though.  So, I’m opening up the comments to them:  Was the quiz useful?  Did you study for the quiz?  How could I make the quiz more useful?  I will try to use this feedback in future years, so please be honest.  Feel free to respond anonymously with a fake email and fake name.

Experiments in teaching: am-I-ready-for-this quiz

I am teaching ‘the grad algorithms course’ for the second time.  It is the first time I am teaching a course for the second time and am excited at finally having the opportunity to fix my previous mistakes.  ‘The grad algorithms course’ is required for all CS Ph.D. students in our department and a prerequisite for any other grad course that I teach.  Last year I had ~30 students.  This year I expected the same, if not less, since I heard that grad enrolment was high last year and low this year.  But no.  First the 35 slots filled up.  Then the 10 slot waiting list filled up.  Then they raised the cap (complete with room change 3 days before term) to 45.  Then the class filled up again.  Cap raise + room change to 49 the day before class.  STOP!

Enrolment has waned back down to 38.  Perhaps at least partly due to my first experiment in teaching, the am-I-ready-for-this quiz.

Last year I was a softy.  Don’t think you have the background for the class?  Give it a try! Come by my office, I’ll bring you up to speed.

I’m not doing that this year.  Sure it will probably save me some time, but mostly I think (hope) it is more fair to the students in the class who do have the background.  So on the first class of the second week, I am giving a quiz on material that is either (a) standard and easy undergraduate algorithms material or (b) very easy for someone to learn in roughly one hour of reading given standard undergraduate algorithms material.  My motivation was from Jeff Erickson’s Homework Zeroes and has the goal of:

  • Formally letting the students know that even though this course may be required for their program and they were accepted to the program, they may need to do some work before attempting the course.
  • Getting the students thinking about algorithms and paging back in their (fond) memories of undergrad algorithms.
  • Getting the students reading material, learning the lingo (particularly if their undergrad courses were not taught in English) before we get into the harder material in the class.

The quiz is next week. I’ll try and remember to report back on how it went.

Announcement: n-th Annual Combinatorial Potlatch 12/11/10 at Western Washington

Last year I spoke at the n-th Annual Combinatorial Potlatch and had a blast.  The informal workshop is a great idea; I wish there were more regional events like them.  Maybe there are and I just don’t know about them.  The n+1-st Annual Combinatorial Potlatch has been announced – I encourage you to go!

This is the first announcement of the n-th Annual Combinatorial Potlatch, which will be hosted by Western Washington University on Saturday, December 11, 2010 in Bellingham, Washington.

We are close to confirming three speakers for the day’s talks and will soon post a webpage with more details and information that will help you plan your visit.

Main Potlatch Page: http://buzzard.ups.edu/potlatch/index.html

There is no advance registration required, nor any registration fee.  The first talk will be mid to late morning, to allow for travel, followed by a no-host lunch, and two talks later in the afternoon.  Many participants choose to stay for dinner locally.

Combinatorial Potlatches have been held for many years at various locations around Puget Sound and southern British Columbia, and are an opportunity for combinatorialists in the region to gather informally for a day of invited talks and conversation. While most who attend work in, or near, the Puget Sound basin, all are welcome.

Program Committee: Nancy Neudauer, Pacific U
Communications Committee: Rob Beezer, U of Puget Sound
Local Arrangements Committee: Amites Sarkar, Western Washington U

Experience Theory Project and Prezi

I’m participating in the Experience Theory Project at the University of Washington right now.

ETP is an event for undergraduates with talent and interest in theoretical computer science, sponsored by the theory groups at the University of Washington and Microsoft Research. The purpose of the event is to exchange ideas about exciting results and research directions in theoretical computer science, and enjoy Seattle in all its summer glory.

Anna Karlin is organizing and asked me to join in.  It’s a great group of students and a great excuse to spend some time at UW and MSR.  There have been about 15 technical talks aimed at senior-year, bright undergrads.1 In an attempt to minimize the time I spend designing talks, I used a new presentation method – Prezi.  I’ve used it before and was perhaps a little too excited about it. As critics would point out, I didn’t take full advantage of Prezi:  I designed this poster2 in Illustrator with a tablet, exported to Prezi as swf and then added “frames” in order to navigate around the poster.  Why?  Prezi was frustrating to work with, figures would have to be uploaded one by one, jpegs cannot be uploaded in high enough resolution to zoom in on, uploading a pdf plain failed.  I was worried about (lack of) reusability.  At least now I have a reusable poster.

There were a few technical issues: I couldn’t use a remote to run the presentation; I forgot to manually set the “sleep” time on my laptop (accustomed to this being automatically set by Keynote); manual navigation sometimes did unexpected, non-deterministic things.  Prezi was cute and flashy, but I wouldn’t use it for a longer talk or a more technical talk.  Overall, I wouldn’t recommend it.

1 The level of the talks, at least on topics of which I am the least informed, was perfect for me – a gentle introduction.  Disconcerting, maybe.  Perhaps I am just too slow to follow the standard (short) technical talk in our field.
2 Which I hope to print out on a plotter and put up in my department. Look! Pretty pictures!

Lessons on writing conference reviews

I’m on the SODA 2011 program committee and finding it, as everything this last year (grant writing, NSF panelling, grad student advising), a condensed learning experience.

Our reviews are almost due which means that this newbie has been through all but a a few of my stack. I asked for subreviews for roughly half my stack and [drum roll] incredibly, despite the procrastinating reputation of computer scientists, my wonderful subreviewers returned all their reviews in to me on time (and several were early).1

The most valuable aspect of these subreviews was not time-saving or expert-opinion-injecting (although that was greatly appreciated), but the stack of example reviews. Sure I’ve seen my share of reviews. But they were all reviews of my papers which has a certain bias. And sure, I’ve seen several reviews of other papers, but they were all reviews written by me. So, after reading this stack of reviews, I can only conclude that I have been a crappy conference subreviewer.

The review should obviously impart an opinion on the paper. But the ideal conference subreview should give enough details of the result to save the program committee member from having to read the paper (or at least, the entire paper). I’m pretty sure I’ve missed this idea writing subreviews in the past; I could cop this up to having never been taught how to write a review but I think it is more a failure of my ability to empathize with the program committee. I imagine I modelled my reviews on reviews of my own papers – in cases where such details were provided, I probably thought “This is boring. I know the results of my own paper, why is the reviewer telling me this?” – when they weren’t, I thought “why was my paper rejected?”2. Embarrassing that it took so long for me to understand this process: subreviews are targeted (mostly) at the program committee member and (direct) reviews are terse because of the large paper load and the ability of a committee member to make an opinion without taking the time to write out a thorough review.

I think a nice addition to conference reviews would be the equivalent of the grant panel summary. Perhaps not so important for accepted papers, but for rejected papers it would be useful for authors to receive high-level constructive criticism (submit to conference X, fix these issues and it should get into conference Y, etc.) Of course, I don’t want to increase the work load of a program committee. At least not this year.

1 One review was a day late but, after all, I could not process all the subreviews in one day, so I would hardly notice or mind.
2 Funny, I don’t have a problem when a paper is accepted!