Category Archives: Silent Glen Speaks

FSM is from OSU

So, when you arrive to Oregon State, in the spirit of, well, school spirit, you’re told of all the things that OSU is known for.  The marionberry, a cross between a raspberry and a blackberry and delicious, was cultivated here and the modern maraschino cherry developed here, too. Two-time nobelist, Linus Pauling graduated from OSU.  It is a land-, sea-, space- and sun-grant institution.  The first graduating class of OSU in 1870 – then the Corvallis State Agricultural College – was comprised of two men and one woman. And so on, and so forth.

But it took a chance encounter at my local food coop to learn that the Church of the Flying Spaghetti Monster was founded by an OSU physics graduate student! Given the worldwide reach of Pastafarianism, you’d think they’d bring that up in the orientation.

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?

NSF Day at Oregon State

The NSF is coming to OSU to hold a one-day workshop on Wednesday, April 13 on the “Foundation, its mission, priorities, and budget [covering] the NSF proposal and merit review process and NSF programs that cut across disciplines”:

This workshop is primarily designed for researchers and educators less experienced in proposing to the NSF; however, more experienced proposers and NSF grantees may well find the workshop useful and informative. It is our hope that events such as this will stimulate new interest in NSF programs at institutions that have not been among our traditional customers, as well as at premier research institutions.

This appears to be open to anyone for the low-low price of $15.  If anyone I might/should know was thinking of coming, do let me know! Perhaps think about giving a talk in our department while you’re here.

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.

Equal access use for bicyclists

The Corvallis City Club hosted a presentation by and discussion with ODOT’s Corvallis representative Jerry Wolcott and Corvallis Public Works Director Steve Rogers yesterday to discuss planned solutions to the traffic ‘problem’ at the main (east) highway entrance to the city.  I put problem in quotation marks because Corvallis is a small town and, while I am not a regular driver, I have never witnessed anything that I would call a traffic jam in town (except during the 6 or so Saturdays on which there are football games).

[iframe http://maps.google.com/?ie=UTF8&ll=44.563138,-123.255873&spn=0.026846,0.038753&z=15&output=embed” 425 350]

The ideal solution (according to Jerry Wolcott) is a $200 million dollar project that would add an overpass and clover leaf intersection to remove the stoplight intersection just east of the Harrison and Van Buren bridges and connect HWY 34 to HWY 20 via a new bridge north of the existing bridges.  This would create a true bypass for Corvallis. Thankfully, funds are short. The stopgap proposal is a 45mi/hr slip lane to allow stop-light-free travel for traffic leaving Corvallis via the southern bypass on HWY 34.

Now, HWY 34 is the only way out of town to the east for bicycles (and pedestrians) as well as cars.  Already, biking along HWY 34 is considered dangerous by most and unpleasant for all.  While it does have gloriously wide, smooth, paved shoulders and is expressly designated as legal for bicycles to travel on according to county maps, it is a high-speed expressway.  I would not recommend it to unexperienced or nervous cyclists.  However, like many Corvallis residents, I do not fall in that category. I have biked HWY 34 countless times to get to the Amtrak train station in nearby Albany, OR.  To do so, I exit Corvallis via the Van Buren bridge and stop at the above-mentioned traffic light.  When the light turns green, I go, along with the rest of the traffic, without having to worry about traffic entering HWY 34 from the south.

Should a slip lane be introduced, my life suddenly becomes much more exciting.  In a risk-of-death way.  I would exit Corvallis via the Van Buren bridge and again approach a traffic light (which would be present to allow traffic approaching the intersection on HWY 34 from the east to turn south).  If the traffic light is green, I would continue straight only to face crossing 45 mi/hr traffic that is merging into the rightmost lane via the new slip lane.  For a car in my position, this isn’t a problem.  The merging traffic must yield.  But as any experienced cyclist realizes, drivers often do not anticipate cyclists.  We are small, slow travelling vehicles (compared to cars).

Now, the plan is calling for connections to a new multi-use path on the north side of the highway.  Huzzah!  But there are problems.  The multi-use path, Susan B. Wilkins Way, that connects the south side of the highway to the north side of the highway passes under the Harrison and Van Buren bridges and is subject to traffic-stopping flooding – an unreliable option for bike/ped travel.  Further, the north-side multi-use path will extend for less than a mile out of town (to Peoria Rd.), forcing those travelling further to cross back over HWY 34 (in the best case, by way of a lighted intersection).  I am not sure how cyclists and pedestrians who need to turn south off HWY 34 between the ‘safe crossing’ endpoints of this multi-use path are expected to safely do so.  Never mind the bulk of those cyclists (myself included) who will shirk the added travel time introduced by this north-side detour and risk crossing the slip lane anyway.

Jerry Wolcott was sure to point out that any change will impact all road users.  The introduction of the slip lane seems to only benefit drivers; that is, there doesn’t seem to be any negative impact toward vehicular traffic.  However, this plan at best, makes bike/ped eastbound travel more inconvenient (by forcing travellers to go out of their way to the north side of 34) and, at worst, less safe (by not providing a reliable alternative and causing bike/ped traffic to cross a 45mi/hr slip lane).  The message to me is: bicyclists and pedestrians are second-class road users.  We are not.  While we may be in the minority, we pay more than our share for road use and are legally entitled to use the roads.

Update: A condensed version of this entry appeared in the Gazette Times.

Looking a gift horse in the mouth

When I was a grad student, I was in a professor’s office when an undergrad stopped by to give the professor an art card as a thank you for writing a recommendation letter.  The professor kindly turned down the gesture.  At the time, I thought that, as the offering was little more than a greeting card, such a denial was not worth the effort.  The professor pointed out that a line has to be drawn somewhere.

I agree.  But I’m unsure of two things: where to draw the line and how to explain the line to students, particularly when cultural differences may play a role.  I’ll describe a few situations that have come up.

I am on the graduate committee for a Ph.D. student along with 3 other faculty.  This involves sitting in on qualifiers and exams and helping to make decisions on their course of study and progress.  Immediately after a qualifier exam some time ago, the student came to my office with a puzzle – having seen that I have a small collection of puzzles on my bookshelf – and offered it to me with a thanks for the exam.  I turned down the gift, explaining that it is not appropriate for me to accept such gestures when I am in a position of authority.  This week, I came back from a week’s vacation to see a gift bag hanging from my office door.  The gift bag contained a card from the same student and alluded to the fact that the bag must have recently contained (a thief in our midst!) the same puzzle.  The student thought it would be ok for me to now accept the present.  I have emailed the student and explained again that I should not receive gifts.  Unfortunately, this time, there is no gift to return!

The Ph.D. qualifier exams here are 2 hour oral exams.  Not the most exciting thing.  It seems to become tradition that the student bring food for the examining committee.  This seems to vary from a few cartons of cookies to full-on home-cooked meals with catered coffee from our building’s coffee shop.  Some may argue that bringing your committee a few doughnuts and coffee may be a nice gesture, and this, apparently, is how this tradition started.  However, it seems to have gone much too far.  Of course, I don’t feel that the committee’s decision would be swayed by the quality of the food provided – if anything, better food may draw a failure from the committee so we might enjoy such a spread once more.  A line should be drawn, but how?  I would argue that nothing should be brought.  As faculty, sitting on such committees is part of our job.  We know that the meeting will be 2 hours and are perfectly capable of bringing our own sustenance.    Any line above zero is particularly strange.  ‘A student may provide no more than $10 worth of sustenance purchased at the building’s coffee shop.’  So is a student expected to spend $10?  Now a student has to bring coffee for the lofty professors?  Any line above zero should be funded by the department, not the student.  That would be great, but I don’t see it in the budget.

Finally, my own Ph.D. student and I have an interesting relationship.  We are very close in age, live around the corner from each other and have a fair amount in common.  We also both enjoy baking, although I don’t find I get to as often as I once did.  We’ve exchanged various food items in small quantities, usually eaten during meetings – neither of us can go more than an hour without eating like constantly foraging squirrels.  On the recent occasion of my entering old age, she brought me a small batch of (delicious, creamy, homemade, peppermint, white-chocolate) fudge.  Perhaps I should have declined the gift, which I felt a little over that ill-defined line, but I didn’t.  I have to say – it made great fuel for a recent bike trip.

What do you do in such situations?  Am I too strict, not strict enough for your taste?