Glencora Borradaile

More exciting news from Oregon State!  Mike Rosulek will be joining our faculty in September.  Mike will bring some great complexity expertise to our department, but it is for his contributions to the fundamentals of cryptography that we recruited him to OSU.  We are building a security group at OSU, and Mike will lead things off.  Mike Rosulek graduated from UIUC in 2009 (yes, we are continuing our Illinois love-fest, it seems) and has since been on the faculty at the University of Montana where he has impressively continued and built his research program in secure computation and was awarded an NSF CAREER award.*

For Amir and I, this will mean the start of a real TCS group at OSU.  I see seminars and reading groups and generally a more lively theory atmosphere in our future here!

* I think that brings our departmental CAREER count to 21.  Given that we have 41 faculty, some of whom were never eligible for CAREER or equivalent, well, that impresses me!

I am super happy to announce that Amir Nayyeri will be joining our faculty at Oregon State next year! Amir completed his Ph.D. with Jeff Erickson at UIUC and has been, for the past year, post-doc’ing at CMU with Gary Miller.  Amir is an expert in combinatorial optimization in computational topology and geometry.  Not only am I excited to work alongside Amir, but our Graphics and Machine Learning groups are also clamoring for more expertise in this area.

As you know, my only complaint about my professional life here has been loneliness.  Amir’s joining us will not only make a huge difference to me, but also my graduate students.  The two of us, I’m sure, will look forward to recruiting more TCS faculty to join us in the future.

Oh, it’s just so exciting!

I hadn’t checked my rss-feed reader since the winter break.  After the (deserved) attention of the life and untimely death of Aaron Swartz, I was interested in hearing the thoughts of my fellow computer scientists and so delved into the hundreds of unread articles in my rss-feed reader.  I was saddened to see that of the 19 personal blogs of computer scientists that I follow, there was only one mention of Aaron Swartz.

Also in the news: driverless cars.  Commentators inevitably rave at being able to read a book or watch a movie on the way to work or avoiding those DUII charges.  You know what has those features today?  Public transit.  And you know what doesn’t help to counter the real problem we are increasingly facing, that of overuse of limited resources?  Private, individual transportation.

More news: Facebook’s new searching feature, allowing Facebook users to access information that other Facebook users have donated to Facebook in exchange for having up to date information about their friends’ pets and drinking Odysseys.  There is a reason why Facebook needed to do this.  Facebook has carved out a segment of the web that is proprietary, that only they allow or disallow access to, based necessarily on their profit margin.

As computer science academics we are in a very powerful position.  We are trusted with shaping the next generation that will make very important decisions that will have far-reaching social implications.  Decisions like those over Facebook’s privacy defaults, motivating technology that enables autonomous private vehicles at the expense of the public interest, defining ownership of electronic media.  We make those decisions ourselves in our research; what we research, how we allow our research to be used.

Aaron Swartz cared about this and I think the world would be a better place if we all took action to advance his ideals.  We can do so by thinking about our actions.  How are you going to get to work today?  What are you going to do when you get there?  How are you going to choose which problems to focus on?  What will you allow your university tech transfer office to do with your IP?  What are you going to teach your students, implicitly and explicitly?

I changed up a few things in my undergraduate algorithms course this year.  I probably wouldn’t have if I wasn’t charged with designing an online version of the same course, one that would be static for at least three years, so far as I understand it.

One major thing that I changed was the assignment component.  This course has always (officially, by way of ABET-geared course learning objectives) included programming assignments.  Something that I abhored.  There was a post by Michael Mitzenmacher that changed my opinion (a bit) on this front. But mostly the thought that non-students would be looking closely at the various components of my course convinced me to take things a bit more seriously.

In previous iterations, I would completely separate “programming” assignments from “non-programming” assignments which is really terrible I know.  So this year I took a 180 and had 4 projects, each geared toward a major topic of the course with design, analysis and implementation/experimental analysis components.  Much better.  (Except for group unfairness woes as mentioned in my previous post.)

For the final project, I left things very open ended.  Design an algorithm to solve (2D Euclidean instances of) TSP.  In class, this allowed me to talk about verifiers (how else would I trust their solutions?), NP, give them a taste of a difficult problem, etc.  The assignment would culminate with a two-step competition. One to solve instances over a period of 24 hours and one to solve instances — live in class — in 4 minutes.  Before the assignment was even released I realized how competitive the students would get, requiring me (a.k.a. our amazing IT guy, Todd Shechter) to set up virtual machines for the competition to ensure fairness.  It was definitely convenient that DIMACS has a large set of instances available with optimal tour lengths listed.  Thank you, experimental algorithms community!

I have to say, I was impressed.  In a stroke of genius, I enforced a 2-page report limit so that I was actually able to easily discern their main techniques.  There were several equivalence classes of algorithms.  Two groups implemented Christofides’ algorithm, and, true to form, it got within 50% of optimal.  I tried hard to keep my impartiality in reading the reports on algorithms by biological metaphor and was pleased to see that my abhorrence played out in algorithms that didn’t do so well.  Several groups that did very well started with some sort of greedily generated tour and then made local changes that improved the tour.  I’d like to highlight the algorithm by Francis Vo and Soo Hyun Yoo, who were the only team to take advantage of the 2D Euclidean-ess of the problem and had an algorithm that outperformed all the others (almost all of the time), solved one of the 4-minute instances to optimality and added fuel to my “take advantage of the domain” banner I love to wave.  They started with a(n almost) convex hull of the points, iteratively added the remaining points to this tour greedily, and cleaned up with local search.  They even animated their algorithm to aid in design:

YouTube Direct

I will definitely make improvements (the in class competition was a little chaotic and not super interesting for the students who didn’t make into later rounds) but I enjoyed it and I think many of the students did.

I’ve just finished teaching our undergraduate algorithms course this quarter.  I changed the course quite a bit from previous iterations.  This was mostly because I have been designing an online version of the course for our online post-bacc degree (more on that in another post).  It gave me a chance to rethink many aspects of the course.  One was in how the project assignments were managed.

There were 4 projects.  Two were rather large and involved and the other two were still challenging, but not as time intensive.  The projects involved: designing, analyzing run times of, proving the correctness of, implementing and experimentally analyzing algorithms using the techniques we learn in class (divide and conquer, dynamic programming, etc.)  I had the students work in groups of 2-3.  Groups were formed in the first class with the only constraint that each group contain one person who self identifies as being better at theory than practice (based on grades in the discrete math and programming intro course sequences).  I did have feedback that the students were thankful the projects were done in groups as they were challenging.

Anyhow, after the first project I started getting feedback of the form “my team members didn’t do any work!”  Unfortunately, I didn’t really plan a mechanism for correcting for this.  The projects account for 40% of the final grade and looking at the current grades, not all the group ‘leaders’ are ahead based on test performance and not all group ‘slackers’ are behind (as I would have thought).  It’s too late to really do much for this quarter, but I would like to be prepared for next time.

I’ve kicked around some ideas:

• Have the groups be randomly assigned and change them for each project.  At least then a given student would be unlikely to be always stuck with a slacker, but a slacker could still ride the coattails of the rotating groups.  I do this in my graduate class, but there the tests are worth much more and I don’t want to do that for an undergraduate class.  Also, the last project is the most difficult, and I would like groups to establish a good working pattern by then.
• Take feedback from groups on who the ‘slackers’ are after the first project and take the ‘leaders’ of those groups and have them form new groups amongst themselves and take the ‘slackers’ and do the same.  I think with this the slackers would end up being forced to work or be penalized and the leaders would get a break.  It might get complicated though.  It would likely piss off some people.  Doing so only after the first project might not be sufficient.  The groups of ‘leaders’ may not be big enough to form new groups.
• Have the groups distribute the points for each project among the members of the group orhave a group participation score incorporated and based on group members rating each other. I’ve heard of these mechanisms being used but I’m not sure how successful that would be.
• Have a graded question (either on the midterm or as a quick start of class quiz on the day of the project hand-in) that would only be easy to answer if a student was involved in the working of the assignment.

I’d love to hear your thoughts.  Or am I over-thinking this and should care less?

Last spring and summer I instituted “my time”.  I started scheduling off 3hr blocks of time 2-3 times a week on my calendar for research.  This happened around the time that I started making my calendar available so students would know when to find me.  (It has made scheduling meetings very easy.)  But I wanted to make sure that I wasn’t interrupted arbitrarily.  I treat these blocks of time like any scheduled meeting.  They are precious.  I will only cancel one or intrude on one for very important things (such as working with collaborators on research or attending a graduate exam).

My productivity went up, I found.  I knew I could rely on a decent chunk of time regularly.  Before, I had found myself with useless one hour blocks squeezed between meetings – not enough time for me to think seriously about a problem.

For some reason I stopped in the fall.  I probably just forgot to reschedule the time for the quarter, with new committee and teaching schedules to work around.  Last week, I was reminded about the importance of uninterrupted time for the creative process from John Cleese’s surprisingly relevant-to-research speech on creativity, posted by Luca.  So, “my time” is reinstated.

Of course, that’s no excuse to waste precious minutes of “my time” writing this post.

Our department is hiring:

The School of Electrical Engineering and Computer Science invites applications for several tenure-track professorial positions in Computer Science. We are building research and teaching strengths in the areas of programming languages, databases, software engineering, computer systems, computer security and privacy, and algorithms.

There are also several openings in ECE and across the university (in case you have a two-body problem).  OSU’s enrollment has been growing, and so the faculty is growing with it.  A large, disproportionate portion of the growth has happened among incoming ECE and CS freshman, making our program (which has a fixed number of spots for juniors and seniors) more competitive.

Please spread the word and have your students and colleagues who want to live in paradise apply now.

As of September 1, our campus is now smoke-free. OSU is joining over 700 campuses across the US with the same policy: no smoking on campus, inside or out.  It is definitely welcome to me, for both public and personal health reasons.  I’ve never understood why people still adopt smoking, knowing full well how many negatives it comes with.  And I’ve never appreciated the clouds of smoke at the doors of buildings.  I wonder what the border of campus will be like though.  Are there enough smokers on campus to make a qualitative change along the commercial roads nearby?

This isn’t the most serious question, but when writing a grant (without a co-PI) do you use the royal editorial “we”?  Or do your refer to yourself in the first person?  When citing your own work, do you use your surname or do you say “the PI”?  When writing a grant with more than one person, do you refer to “the PI” and “the co-PI”?

In the grants I’ve read, I’ve seen both.  The ones that use “the PI” and “I” generally sound more confident and strong.  But there is some discomfort to me in doing so.  A little too cocky.

Or tell me to stop quibbling, Cora, and get back to writing.

I’m on my way back from the 3rd Women in Theory biennial conference. I was invited to the first one, as a participant, but was unable to go due to a combination of teaching my first course, recovering from mono and generally travelling too much in the early months of my post doc. While I’m sorry to have missed that, I am very happy to have been invited this time as a speaker.

The speakers were a cross section of career stages from junior faculty through well-established researchers and covered an array of topics in TCS from algorithms through security. And though the conference was targeted at the 40 or so grad students (only three of which were near graduation), I appreciated the chance to hear survey-ish talks and advice from the panelists (on which all the speakers sat) and meet the next generation of TCS leaders. Well, at least a targeted selection thereof.

Now, I know that such gender-targeted events garner criticism. Is it discrimination to not have male speakers and participants? You probably already know my opinion, but I’ll repeat it here. The gender balance is bad. It’s gotten worse at the undergraduate level since the 80s and 90s and is only very slowly heading toward balance at the graduate and faculty level. Any proponents of the “an unbalanced ratio is possibly the ‘natural’ ratio” can look at any number of fields, (chemistry, medicine, biology) to see that what once was an unbalanced ratio is now balanced. The unbalanced ratio results in discrimination, either explicit or subtle, which causes the numbers to grow ever slowly. Targeted programs and efforts help to overcome this discrimination. The imbalance hurts our field and any field that suffers this problem*. We are missing out on an untapped resource of talent. The Eva Tardoses and Jennifer Chaves and Cynthia Dworks of our world are not anomalies.

I digress. On Monday afternoon, I spoke to a room of 50 women. I have never spoken in front of 50 women before, despite having taught classes upwards of 200 students. In my classes, when I’m feeling lazy and don’t target students to answer questions but just draw from the hands that go up, I don’t get questions or answers from female students. But in this room, many answers. Many questions. Many volunteers. I don’t think I’ve ever felt so at ease giving a lecture before.

I decided, rather than give a talk delving into the details of my own research, or giving an overview of an area, I would give a tutorial. So, I picked up some chalk and taught planar graphs, their properties and how they can be used to design algorithms, for 90 minutes. It went well! I got many blush-inducing thanks after and that made me feel really, really good. I hope others can experience that at some point.

So finally, thank you to Shubhangi Saraf, Tal Rabin, Lisa Zhang and (local organizer) Moses Charikar for making this happen. I do hope it continues to, and I wouldn’t mind at all if it was expanded to have all levels included as participants, because I’d love to go back.

* I have to say that I am very curious as to how a field, such as English, where the gender balance is essentially inverted from our own, handles any discrimination that may arise toward men.