Tag Archives: tcs

Inoffensive stable matching

I like to start my grad algorithms course with stable matching.  It is a beautiful, clean, practical algorithm.  It can be covered relatively quickly and give an overview of the basics of algorithm design and analysis.  I love it.

What I hate is that every treatment of stable matching available online and in the textbooks in my office is presented as the stable marriage problem with men getting matched to women and men getting their best possible match and women getting their worst possible match.  Seriously?  This algorithm that is used to match children to schools and medical students to residency programs and dental and medical specialists to hospitals and students to universities and lawyers to law firms and rabbis to congregations (or so I’ve been told)?  We need to teach this algorithm as an exercise in heternormative, sexist coupling?

If half our field were women, do you think women would be repeatedly getting the shaft in this lesson plan?  If we didn’t need It Gets Better in our society, would we be proscribing to man meets woman, man proposes to woman, man marries woman?  If we lived in a dreamy society that didn’t spend one-third of Africa’s debt each year in the wedding industry, would we be using this metaphor?

So, here you go: very basic, stripped-down lecture notes on the Gale-Shapely algorithm that matches jobs to candidates.  (Written quickly, corrections welcome.)

If someone could change the wikipedia page on the problem from stable marriage to stable matching, I would be much appreciative.  (My wikipedia skills are no match.)

Update 9/22: To clarify, it is the United States that spends (on the wedding industry) an amount equivalent to one-third of Africa’s debt.

Update 9/25: Jeff Erickson presents stable matching using doctors and hospitals.

Update March 2015: Motherboard picks up the story.

How do you find conference acceptance rates?

It’s getting to be that time.  Mid-tenure.  I apparently am supposed to include acceptance rates for conference publications.  Google got me about half the numbers, but for the rest … is it annoying to email the program chair for that conference?  Even if it was a few years ago?  How else would you find out?

Update 9/22: helpful links and suggestions in the comments below!

Responsibility for versus responsibility to

I received some advice from an established biochemist via a friend in regards to the stress related to advising graduate students.  See, of the new tasks in the past year, graduate advising has been the most stressful for me.  I feel this weight of a person’s career in my hands.  What if I pick the wrong problems?  What if wreck their confidence?

But the advice lifted a weight off my shoulders: you are not responsible for your students, you are responsible to your students.  You don’t have control over whether your students engross themselves in their work, whether they read papers beyond the ones you explicitly say to “read this”, whether they will really focus on their research – you can’t be expected to be responsible for this.  However, you can read and edit their writing, suggest papers and books to read, introduce them to your colleagues, teach them.

It was a simple change in propositions, but it made a big difference for me.

On a somewhat related note, I’m planning on taking up Matt Welsh’s advice on evaluating grad students.  He advocates setting goals on a quarterly basis and remarking on how well those goals were met.  I think this will work well for concrete items such as writing up a paper for which proofs have already been established and completing qualifiers, but how should we set goals for work that may or may not be possible (ie. “settle this conjecture”)?

Conversations with other theoretical computer scientists

Claire Mathieu caught me on IM a few weeks ago – she was in the middle of a discussing a quote with Valerie King by Sheryl Sandberg, the COO of Facebook, at Barnard College’s commencement.  You can read our discussion on Claire’s much-more-prolific-than-mine blog.  I’m not sure at what point it became clear that this discussion would become a public blog post, but I did want to point out that as a result of the public-ness a lot of my comments hit the editing room floor. (Hence my relative silence in the edited conversation.) Why?  Not because of my crude mastery of the English language.  Or not only, at least.  Mostly due to tenure concerns.  We had some email exchanges to decide whether that was necessary – I ended up playing the better-safe-than-sorry card.

I wish that wasn’t the case.  I don’t think that my opinions were particularly worrisome, but apparently there is an undercurrent of reservation pre-tenure.  Which doesn’t seem like a psychologically healthy thing or – in the more professional aspects of research direction – a limiting factor for the field.  This came up in a second conversation with Claire on choosing research problems.  (A conversation I entered knowing it would be made public, so less was cut.)  In humming and hawing over the decision (which really didn’t take as long as I’m making out it did), I alternated between “Maybe it’s better that people say things like that in public?” and “Should I be more reserved?”.

Anyhow, these conversations have been great for me – a wee bit of mentoring-like contact over the distance.  Hopefully there will be more. Overall, a reminder that the positives outweigh the distractions of staying signed into IM.

Lecture notes for Baker's technique for PTASes in planar graphs

In teaching so far, I have relied almost exclusively on textbooks and other people’s lecture notes (Jeff Erickson comes to mind, again and again) for providing materials to my students.  Yes, I would recommend this to anyone who has not been teaching for too long.  Preparing lecture notes that are hand-out-to-your-students worthy is time consuming!  Especially when you are a perfectionist.

I’m teaching a grad course on approximation algorithms right now, using Vijay Vazirani’s book.  (Yes.  Those of us on the quarter system are still teaching.)  I wanted to teach Baker’s technique for giving PTASes on planar graphs as it is beautiful and close to my heart.  By heart, I mean brain.  I only wanted to spend a lecture or two on it and my students don’t know what treewidth is.   The only lecture notes on this that I know of are Philip Klein’s and (stubbornly), I needed something more self-contained – that didn’t build on a course’s worth of notation and background.

So, I prepared these notes on my wiki teaching page.  I don’t prove that k-outerplanar graphs have treewidth 3k-1 or even define treewidth, but I show a simpler version of solving maximum-weight independent set on something I call k-innerplanar graphs.  I think it gives the intuition and ingredients of the full picture without getting caught up in too many details.  If anyone spots a bug, inconsistency, etc, please let me know.

So, yes, basically I am announcing “Ooooh look at me!  I’m doing something everyone else has already done time and time again!”

A lens on the sciences

The workshop on Theory of Computation as a Lens on the Sciences at Berkeley was this weekend. For the three people out there that haven’t seen Christos Papadimitriou’s talk on the same, I recommend it.  A follow-up to a focus on the use of theoretical computer science as a methodology for study in seemingly distance fields (economics, physics, biology, etc.), Richard Karp, who opened the festivities, lauded the near-decade-long effort that has (among other acheivements) motivated new programs at NSF.

I was only able to attend the first day.

Ehud Kalai started and end with the same question “are games too hard to solve?” and while admitting that the answer has remained “yes” for decades, argued for the value in studying simple(r) classes of games that allow predictions and solutions, presumably offering intuition for more complex and realistic games.

Christos Papadimitriou was entertaining, as usual, giving an overview of the ties between economics and TCS using the examples of sponsored auctions and selfish routing.  I’m hoping they will post slides or videos (the talks were being recorded, so I imagine this will be the case) as he gave a great quote on nobody having an incentive to change if nobody changes.  (As an advocate for alternative transport, this is a sentiment I’m often up against.)

Tim Roughgarden “discussed”, including the short history of sponsored search and referred the to “turn of the century”.  I sat confused for a few seconds … turn of the century … how did sponsored search come to be studied at the turn of the century … oh … turn of the current century … have I ever used that phrase to describe 2000? … certainly not … have I heard anyone used that phrase to describe 2000? … I must be getting old … hang on … Tim Roughgarden is older than me … do I live under a rock?

The next two two talks were on avenues of research unfamiliar to me.  Les Valiant spoke on attempts to study evolution (yes, the biological one) using ideas from learning theory.  I was rather skeptical of the model of evolution under study (as was a questioner after the talk), but I’ll give the benefit of the doubt that studying simple models can lead to some intuition.  I just hope that anti-evolutioners don’t take any results out of context as ‘proof’ for in the invalidity of evolution.  Michael Kearns discussed the use of crowd sourcing to solve graph problems in a local method.  His primary example (with actual experiments with actual people – crazy, right?) was graph colouring, where each participant is a node and can only see the neighbouring nodes.  Perhaps surprisingly, the crowd was not able to 2-colour a circle, but was able to 4-colour a preferential attachment network.

The most entertaining talk for me was Mark Newman’s.  On the structure of actual networks (both natural – biological, social – and technological), his talk shed light on some interesting properties and motivations.

  • The small-mouth bass is cannibalistic.  Food chain networks need self-loops.
  • Interesting networks almost always have one big component – for if it had several big components, the chance that no edge crosses between those components is low, and if it had no big component, no one would be interested in studying it.
  • In epidemiological graphs, the interesting quantity is the square of the degree: a person of high degree is both more likely to catch and more likely to pass along a communicable disease – each proportional to the degree.
  • Social networks have positively correlated degrees – popular people have popular friends.  Technological networks have negatively correlated degrees – most neighbours of hub nodes are spokes.
  • Only 40% of friendships are reciprocated.  Get on board, facebook.

So thanks to Berkeley for hosting.  I’m loathe to complain as the talks were excellent (despite being free), but I would ask for more clear breaks … 3 hours straight of talks makes a trip to the restroom tricky if you are sitting mid row.  Of course, unlike the mens’ room, the ladies’ room was not going to have a queue, with only one female speaker (on day 2) and my estimated gender (im)balance of 20:1. Surprising given the high ratio of students present.  Berkeley, Stanford, etc … are your numbers really so off?

Topology through crochet

crochet mobius stripA good friend taught me how to crochet on Sunday night.  I started with the classic square-to-be-used-as-a-dish-rag project and moved onto the spiral-to-be-used-as-a-pot-stand project. Project number three? The Möbius Strip. Now, I understand the Möbius strip well. What kid has not taken a strip of paper, twisted it, taped the ends together and then drawn a line starting on one side of the paper only to seamlessly (or edge-lessly) reach the other side? I started crocheting the Möbius strip by creating a line and then joining the ends of the line, adding a twist to the line (a 1D Möbius strip?). I then continued crocheting along one edge of the cycle. But of course, since a Möbius strip has only one boundary, I could continue extending the thickness of the strip by spiralling outwards.

I thought: what would happen if I started dropping stitches, making this boundary shorter and shorter? Well, the Möbius strip is a non-orientable surface with one hole – that forms this boundary. I reminded myself that the Möbius strip is surface obtained by puncturing a projective plane – the non-orientable surface of minimum genus – however, I never had a good intuition of what the projective plane is. Let me tell you though, after dropping every fourth stitch on the boundary of my Möbius strip, I started having a pretty good idea of what a projective plane does.

crochet punctured projective plane 2crochet punctured projective plane 3crochet punctured projective plane 1

I couldn’t continue until the boundary closed up – for obvious reasons – so I still have a Möbius strip, but the physical surface is close enough to the projective plane that I get a much better feel for what that means.

I’m not the first person to crochet a Möbius strip – apparently it is a popular scarf design – nor am I the first to explore geometry with crochet. But I have to say that actually creating this surface adds an intuition I’m not sure you could get elsewhere. Finally, if you haven’t seen Margaret Wertheim’s TED talk on math, crocheting and coral including how to crochet a hyperbolic geometry and in which she says

So here, in wool, through domestic feminine art, is the proof that the most famous postulate in mathematics is wrong.

I highly recommend it.

A flat 6-pack of SODA

Rightly chastised by Suresh for not blogging while at SODA [1] – enough time has passed for me to completely forget anything I might have wanted to say. But the timing is perfect. I am procrastinating writing a paper that I do not wish to write [2]. So here are six (not necessarily technical) things that I learned at SODA this year.

  1. The crossing number of K13 is unknown! This gem from Tasos Sidiropoulos’ talk on his work with Julia Chuzhoy and Yury Makarychev studying the approximating the minimum number of crossings required to draw a graph on the plane.
  2. John Hershberger lives in Portland!  Maybe not so exciting to you, but for theory-starved me, it is very exciting to learning that there is an algorithmer nearby.
  3. It is still possible to give a more efficient, deterministic, optimal algorithm for simple problems in general graphs. Monika Henzinger spoke on her work with Krishnendu Chatterjee on maximal end-components (like strongly connected components, but not). Later in the same session I was delighted by Valerie King’s laugh when a youthful speaker referred to a work of hers as ‘classic’.
  4. Listening to a talk with the goal of asking one or two questions results in increased attention and a deeper understanding of the material. I learnt this while acting as the MC for 1 ALENEX and 3 SODA sessions – knowing that I’m always left sad after giving a question-less talk, I wanted to make sure that I had a question ready for each of my speakers.
  5. There are still problems that we don’t know how to solve in bounded treewidth graphs: (a) thin trees (which can be used to solve the asymmetric travelling salesperson problem) as pointed to by Shayan Oveis Gharan in his work with Amin Saberi on the ATSP problem in surface-embedded graphs and (b) prize-collecting Steiner forests which are (among other things) shown to be APX-hard in bounded treewidth graphs in Bateni et. al’s work.
  6. 40% of Princeton students take first-year computer science and this course has the second-highest enrolment at the university.  Okay, this one wasn’t from SODA, but from ANALCO’s keynote talk by Robert Sedgewick. I have dreamt (in my teaching statement) of bringing such a stat to Oregon State University.  Now I have ammunition for the people upstairs [3].

[1] I decided to travel without my laptop and thought that painfully poking away at my touch phone would be a bit ridiculous.
[2] But should.
[3] Actually downstairs.

PC innocence

I’ve long been meaning to remark on my experiences of being on the SODA and ALENEX program committees this past year and fellow bloggers recent reflections on PC membership encourages me to finally post what little I have to say.

I went into the SODA PC expecting a lot of work.  I (mostly) cleared out a full month to do the reviews, which was not much less than the time allotted to finish the reviews.  Of the 48 papers [1] I had to review, I had approximately half sub-reviewed.  My sub-reviewers were amazing (timely, thorough, etc).  What I didn’t expect was the amount of time that went into discussing the papers.  With the virtual committee-meeting spanning roughly 3 weeks, I spent a lot of time going over those subreviewed papers, reading other PC member comments and adjusting or defending my opinion.  Since I didn’t plan for this, I didn’t have a lot of time to spend on it.  There was great potential to learn from the papers submitted and committee decisions, but the overwhelming amount of work didn’t leave time to synthesize conclusions at a higher level.  And then classes started up.  While it was a worthy experience, it doesn’t quite rise to the bar Claire experienced with her first SODA committee.

I think a physical PC meeting would have added the benefits that Bill highlights by developing a relationship with those members I didn’t previously know (which is many of them).  I still had the benefit of getting to know Dana Randall, who, although I have nothing to compare it to, did an amazing job and provided wonderful guidance along the way.

The ALENEX PC was much lower key.  13 papers to review.  And though getting subreviewers proved mostly futile (I think I managed to get 3 subreviewers – most of my emails for ALENEX were left unresponded to or turned down), the papers were slightly easier to review and I came out of the experience with a much better idea of what an experimental paper should look like.

I know our community has discussed the possibility of a tiered PC for STOFOSODA.  While I don’t know what the implications really would be, I can say that a less daunting experience (such as in a lower tier) would be preferable for a first-time PC experience.  I suppose one could emulate this by starting with workshop and smaller conference committees, but I think it is great that STOFOSODA has a history of including junior researchers on their PCs and one should hardly pick-and-choose when they are offered the chance to serve on their favourite conference’s committee.

[1] Yes, 48, oh ye in other fields with hierarchical committees.

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

One of my experiments in teaching this quarter was to have a quiz the second week of class on material that I considered so basic, that if you couldn’t do very well on the quiz, well, you may well consider (re-)taking the undergrad algorithms course first.  A few students with lower scores on the quiz did decide to drop the class.  Well, term is over now and I can see how good an indicator this quiz was.

Shown below are the student grades on the midterm and final (y-axis, midterm ‘o’ and final ‘*’)  vs the quiz score (z-axis) – plots are linear.  The brighter the shade of green for the vertical bar connecting a students exam scores, the higher the final grade for the student.  While there are a few outliers, I think that I wasn’t wrong in saying that a low score on the quiz may indicate that you aren’t ready for grad algorithms.  What you can’t see as well here is that the midterm scores were quite linear with the quiz – not as surprising as the midterm covered material that I would expect starting CS grad students to know anyway.

So I’ll probably do this again next year.  I’m better informed though.  I’d like to include a few harder questions to give a better indication of mathematical maturity than this year’s version provided.  My goal?  A perfect indicator, so that I can skip all forms of evaluation and simply assign the students a grade based on the first quiz.