Tag Archives: tcs

Discrimination and the conference publication system

After Trump’s travel ban was upheld by SCOTUS, I started thinking of ways that we could materially help our affected students and colleagues. Those on visas from “banned” countries are at best stranded. But it goes from bad to worse quickly. Will their parents be able to visit? Will students on F1 visas be able to use CPT and OPT for internships? Will those on H1s have any chance at permanent residency?

Of course, I’m reminded that for students studying in the US on single-entry visas from many more countries than just the “banned” countries, including China and Vietnam, life has always been difficult. For a trip home, you many need many months (and an understanding advisor) to have time to reapply for a visa to return to your studies. Your parents may not be lucky enough to get a visa to ever visit you. And those conferences that are out of the US? Well, those are likely impossibilities, and this greatly impacts your ability to publish and network.

And how about non-US based researchers who are citizens of banned or otherwise unwelcome nations? Can they as easily attend US conferences, such as STOC, FOCS and SODA, which are almost always in the US?

So what we have is a conference publication system that is structurally discriminating, as a result of the institutional discrimination of US border control. (If the notion of individual, structural and institutional discrimination are new to you, here’s a short explanation.) US law restricts the travel of people based on their country of origin and current residency status (institutional discrimination). Our field, for people to succeed, depends largely on their ability to publish papers. Since conference publications are heavily weighted and since every conference I can recall submitting to has a “one author must attend the conference to present the paper” rule, one’s success depends on one’s ability to attend (or have a co-author attend) the conference (structural discrimination). And since conferences are so normalized, it is expected that junior researchers will do the attending and presenting as much as possible so that other people “get to know you” (again, structural discrimination).

But the discrimination doesn’t end there. We have heard reports of the individual discrimination that women face at conferences (for example in statistics and machine learning and theoretical computer science). You don’t have to be an idiot to understand (or you can dig up the science that will help you accept the fact) that when someone faces individual discrimination, often they will avoid the situations where they face that discrimination.

And never mind the myriad of other reasons why people can’t or choose not to attend conferences: disability, care-taking responsibilities, shyness.

Let me spell it out. In order to really succeed in most areas of computer science, you need to publish conference papers and this, for the most part, means attendance at those conferences. But because of the institutional discrimination of border control laws and the individual discrimination that individuals face and the structural discrimination that others face, computer science discriminates based on nationality, gender identity, disability, and family status, just to name a few aspects of identity.

Tell me, how does that discrimination help advance science?

Until we get serious about making real structural changes — fundamentally changing the way in which we are expected to disseminate our work and how our work is evaluated — I fear that we will be discussing the same issues of representation in computer science for decades to come. Perhaps in the past, it was most efficient to share ideas (among mostly white, mostly male) scientists by gathering them together at a conference. But now, in the age of email, videoconferencing, instant messaging, and arXiv, its a little ridiculous that we cling to such old fashioned modes.

So while I don’t have an immediate idea to help students and colleagues impacted by Trump’s “constitutionally sound” travel ban, we could make some positive change for those and others, and computer science more broadly, in making conferences an exception rather than the rule.

Teaching Communications Security and Social Movements

My reaction to the Snowden disclosures was a mix of “I’m not surprised” with “this is a lot worse than I imagined”.  Not long after, I went to a small workshop and during breaks tried to engage colleagues in discussing the implications of the capabilities of the surveillance state of which we were now at least partially aware.  Responses were at best disappointing.  The near-universal apathy was disturbing.  Most of the people I spoke with teach undergraduate computer science.  If they don’t care about the ethics of a surveillance system whose maintenance and expansion depend on our graduates, what hope would there be for change?

In thinking, “what more can I do from my highly privileged position?”, my partner and I have been teaching activists in social movements to use end-to-end encryption and other online self-defense techniques.  We’ve also designed a freshman course to teach online self-defense.  Since we are in particular concerned with the impact of state surveillance machinery on social movements, the course is offered through the Difference, Power and Discrimination (DPD) program at OSU and so addresses institutionalized systems of power, privilege, and inequity in the United States.  We will be teaching the technical concepts for understanding online surveillance and the encryption tools that can mitigate it alongside the historical and contemporary impacts that state surveillance has had on social movements.  The course will be offered for the first time this coming Spring — CS175: Communications Security and Social Movements.

From the reading that accompanied the development of this course and our trainings, it became clear that teaching CS175 through the DPD lens was a good move. Muslim populations in the US are subject to heightened surveillance, scrutiny, infiltration, provocation and entrapment.  The Department of Homeland Security monitors those involved with #BlackLivesMatter.  Historically, we know that surveillance is key to suppressing groups that challenge the state (for example, the Black Panther Party and the American Indian Movement) and the mass collection of data on targeted populations has facilitated genocide.  Mass surveillance doesn’t affect us all equally — mass surveillance is disproportionately directed at marginalized groups such as people of color.

To hear about this in our College’s new podcast, start listening here at 15:10.

Work is work and it shouldn’t be expected on the weekends

written on December 27, 2013 and saved for publication until tenure

A month or so ago, the STOC’14 PC chair took an informal poll of when we wanted the PC meeting: Friday & Saturday, Saturday & Sunday, Sunday & Monday. What the hell?  Why not any two day combinations that don’t include a weekend day?  So it doesn’t get in the way of work?  What on Earth do you think a PC meeting is if not work?  So it doesn’t get in the way of teaching?  I am pretty sure all our department heads want us to go to conferences and take part in program committees and will happily accommodate a cancelled class or two or a sub by a graduate student or colleague.

My response to the PC chair was: “I would greatly prefer Fri-Sat or Sun-Mon so it doesn’t take the whole weekend away from me.”  In the background, my partner works in Portland during the week, and so we live apart during the week, and the weekend is the only time we have together.  Also, committing to work a Saturday/Sunday combination means 12 straight full days of work (on top of the cross country flight the program committee means) since taking a weekday off to compensate for the weekend is very difficult to arrange — guilt kicks in and I would inevitably work.  On a very serious note, down time is key to “work life balance” also known as one’s mental health.  We shouldn’t be defaulting to working on the weekend.  Our conferences shouldn’t be on a weekend either.  They should be on weekdays.  Weekends are for rest and weekdays are for working.  Anyone read about the labor movement?  In speaking to friends with kids, particularly dual-career couples, travelling over the weekend is not cool.

You know who doesn’t expect you to work on the weekend?  NSF.  Panels are on WEEKDAYS.  You know who else?  Europeans.  Dagstuhls are run Monday to Friday.  ESA is Monday to Wednesday.  ICALP is Monday to Friday.

So you know what?  If you want to retain more people in our field, and you want to seriously push work-life balance, you shouldn’t plan work events on weekends.  Keep them to weekdays.


Oh, the STOC PC meeting was Saturday/Sunday.  THANKS.

continued January 18, 2014:

Continued annoyance in regards to the STOC PC.  We have been asked, late on a Friday afternoon to pick 2 papers out of a stack of 40 to provide extra reviews.  By Sunday at 3PM.  Seriously?  I know we are all expected to work ALL THE TIME and are supposed to LIKE THAT.  But you know what?  I don’t.  I am tired of this expectation and I would like to protect some time to be free of work commitments.  Choosing papers for STOC is not so important that some task needs to be completed in a 2 day span over a weekend.

continued February 6, 2014:

There has been another emergency “feedback needed within 48 hours” emailed out on a Friday evening.  This is timely.

The negative impacts of random conference decisions

The NIPS experiment is making waves.  If you are unaware, for the last NIPS conference, the PC was broken into two independent halves A and B.  A random selection of the submissions were assigned to both committees.  The result: 57% of the papers that were accepted by committee A were rejected by committee B (and vice versa).

This is terrible for many reasons.  Some reasons that I have heard are the careerist issues (our jobs and promotion depend on accepted papers at top conferences) and the negative impacts on the Rate of Progression of Science.  I’d like to discuss two more reasons:

The random rejection model makes needless work

If the average number of times a paper is submitted to a conference before it is accepted is 2-3, then we as a community are doing 2-3 times more work when it comes to writing & publishing: formatting papers to the will of the conference, reviewing papers, serving on PCs, reassuring students, consoling ourselves over beer. Should we be spending our limited time & resources on this? I do understand that papers can improve between different submissions, but with higher quality, constructive reviews, resubmitting once would be much less a burden. And perhaps if people felt like the system wasn’t so random, we wouldn’t try rolling the dice so early and often.  And perhaps we would have time to do a more thorough job as reviewers.

The random rejection model likely negatively impacts underrepresented groups more

“Just resubmit your papers.”  I worry that this non-solution disproportionately and negatively impacts those in
underrepresented groups. It is known that those in underrepresented groups tend to suffer from more impostor syndrome; and it is known that those suffering from impostor syndrome tend to take rejections on face value (our work isn’t good enough) whereas those in dominant groups tend to blame the rejectors (they don’t know good work when they see it). We also (should) know that small things can have big effects.  One freshly minted professor emailed me:

I have personally experienced this during graduate school and I’m sure I and my students will experience this in future. A second or third year student puts in about one year worth of work with the hope that he/she will have his/her first top-tier (FOCS or ICML) conference paper soon. The rejections and bad reviews can essentially kill the confidence of that student. To some extent, this can also happen to the junior faculty.

One colleague worried about students dropping out of science altogether as a result of this.  On a personal note, I have definitely changed my publishing behavior to favor journals where, although the time lag can be great, comes with a discussion between author and reviewer via the editor. I have only had one ‘bad’ experience with trying to get something published in a journal. I would say that I’ve had a ‘bad’ experience with at least half of my conference submissions.  I have taken to rolling the dice once, if at all.

Add this together with our lack of double-blind reviews in TCS, we may be doubly hitting underrepresented populations, whose work is more likely to be dismissed by a dominant-group reviewer.

We should fix our conference system.  Or just trash it altogether.  I’d like to point out that the latter option would be better for the planet.

Source for open-source textbooks for computer science?

My soon-to-defend Ph.D. student, Theresa Migler, pointed me to the Open Textbook Initiative by AIM, with the question as to whether a similar resource exists or is in development for computer science.  I am now forwarding that question to you.

The Open Textbook Initiative looks awesome.  It is more than just a collection of textbooks that are available freely.  The textbooks are vetted against a set of reasonable criteria, including (but not limited to):

  • able to serve as the primary text in a mainstream mathematics course at the undergraduate level in U.S. colleges and universities
  • have exercises
  • be class-tested and have been used (and be in current use) by faculty other than the author

I think this is a great direction to go in.  Peer-reviewed and peer-tested classroom resources, available freely to all.  These are exactly the types of resources I limit myself to for my courses (although, it isn’t a limit of quality).  Currently I use:

All of these, I think, meet the OTI criteria.  Do we have a similar group that vets open textbooks in CS?


The ball-coverage property and a great journal turnaround time

Erin Wolf Chambers and I had a paper accepted yesterday to the journal Discrete & Computational Geometry, a journal I now highly recommend.  This entry is a story about that paper as well as the journal.

In a keynote talk at CanaDAM 2011, Stéphan Thomassé referred to the following theorem of Chepoi, Estellon and Vaxès:

Any planar graph of diameter at most 2R has a subset of O(1) vertices such that every vertex in the graph is within distance R of that subset.

We’ll call this coverage of the graph by O(1) balls of radius R the “ball-coverage property”.  The proof is quite deep in that it calls on the fractional-Helly property of the set system of radius-R balls.  In his talk, Thomassé states that the constant is not computed in the paper, but was done so by a student.  I don’t remember the exact number, but it was around 800.

Surely that can’t be the right number.  I worked for a while on coming up with a different, more direct proof that would result in a better number.  Something reasonable.  Like 5.  Or 7.  The best known lower bound is 4.

I haven’t been successful.  Erin and I, in our first successful collaboration which involved an allergic reaction to St. Louis (actually to a hand cream, not St. Louis), generalized the result to bounded genus graphs.  That is this paper.  We thought we had it generalized to clique sums of surface embedded graphs … we can handle apices, but vortices and clique sums proved … tricky.  As they seem to be.  But I would suggest that minor-excluded graph families have the ball-coverage property.

We had this result written up in the summer and debated where to send it.  SoCG was out as Erin is on the PC this year.  Rather than wait for a spring submission, we decided to go straight for a journal.  We submitted to DCG on October 22, 2013.  We were asked for what turned out to be minor revisions on March 12, 2014 and resubmitted on March 19.  The final acceptance came in on March 31, 2013.  Just over 5 months from first submission to acceptance.

That is comparable to the roughly 3 months for conferences, with the added benefit that you can actually have a back-and-forth as needed with the reviewers through the editor.  No rejections based on misunderstandings.  No rejections based on “we only have X spots”.  No rolling the dice.  And no travel to yet another far away conference.

If only more journals were like this.  If only conferences were more about giving a place for people to meet (regionally as well as internationally) and less about picking the X top papers without a truly full review even though it is treated like a fully published result … well … that would be great.

Conversations with graduate students

A male graduate student told me he started taking a yoga class only to find that there was only one other man and the remaining 29 were women.  He said he didn’t feel like he belonged and so he dropped the class.

A female graduate student at SODA told me she didn’t see a single talk by a woman and she didn’t feel like she belonged.

(There were talks by women, but with 3-4 sessions, and none of the keynotes by women, well, they can be easy to miss.)

Bringing current events into the technical classroom

I spent last summer thinking about how to bring something related to the climate crisis into my fall undergraduate algorithms class.  In this class, I have converged on having 4-5 projects covering iterative, divide and conquer, dynamic programming, linear programming and heuristics.  These projects each have a practical component where an algorithm is implemented.  Linear programming seemed to be the tool that I could use to “solve” some problem in climate change.  It wasn’t until I stumbled upon this article by Robert Vanderbei suggesting an upper-level class project wherein students fit a curve to daily temperature recordings.  The suggested curve is the superposition of

  • a sinusoidal curve with a period of one year to model the change in seasons,
  • a sinusoidal curve with a period of 10.7 years to model the solar cycle, and
  • a linear term representing any drift in mean daily temperatures.

I adapted the suggested project to my class and had them fit such a curve, using GLPK, to 60 years of daily temperature recordings for Corvallis.


I provided the students with the data and offered bonus credit for students who repeated the project for another location (downloading data from NOAA).  The students found the project challenging but seemed to appreciate the tangibility of the project, so I think I will likewise adapt other projects. The students could then interpret the coefficient of the linear term as the amount of warming in average daily temperatures.

A few interesting things came up.  For example, apparently two different versions of GLPK find two different “optimal” solutions to the same LP — with different values.  For more details, please see the project description.

Next year, I think I will have them choose their own location by default as I think it is a useful experience to clean data …

Undergraduate algorithms study guide

A year ago, I was just finishing putting together materials for the new online version of our undergraduate algorithms course.  I’ve finally compiled all that material into one webpage: available here. There are a few things not yet posted, but this is essentially the content of our undergraduate algorithms course less the assignments and exams. As when I teach the on-site course, I relied heavily on material from others, notably:

Though the “interactive questions” were written by me, they were not implemented by me.  I have to thank Oregon State University’s eCampus group for that.

Hopefully this will be helpful to others, though it assumes the particular prerequisites of our program …

Women in Theory Workshop: Call for Participation

via Lisa Zhang, Tal Rabin and Shubhangi Saraf:

The Women in Theory (WIT) Workshop is intended for graduate and undergraduate students in the area of theory of computer science. The workshop will feature technical talks and tutorials by senior and junior women in the field, as well as social events and activities. The motivation for the workshop is twofold. The first  goal is to deliver an invigorating educational program; the second is to bring together theory women students from different departments and foster a sense of kinship and camaraderie.

The 4th WIT workshop will take place at Google New York, May 28 – 30, 2014, in coordination with NYU and Princeton, right before ACM STOC 2014.

Confirmed Speakers: Lenore Blum (CMU), Julia Chuzhoy (TTI), Shafi Goldwasser (MIT), Orna Kupeferman (Hebrew U.), Katrina Ligett (Caltech), Rotem Oshman (U. Toronto), Vera Sos (Alfrd Rnyi Institute of Mathematics).

Important dates:
Application deadline:  January 20,  2014.
Notification of acceptance: February 10,  2014.
Workshop: May 28-30, 2014.

For more information see https://womenintheory.wordpress.com/ or contact  womenintheory2014@gmail.com.  I attended WIT as a speaker in 2012 and had a wonderful time.  I wish it was something I could go back to every year!  I highly recommend you encourage your graduate students to go!