Category Archives: Silent Glen Speaks

Donation price of anarchy

I recently went to a Christmas party where, instead of a gift exchange, there was a donation exchange.  Essentially, we each placed a cause’s name into a hat, people draw the names and are asked to donate to the cause.  You may donate any amount you wish (including nothing if you are particularly opposed to the cause you drew).  Given that this a group of people that have collectively decided to opt for altruism, the honour system should work.  As a result, I will be donating to the World Food Program and someone will be donating to Planned Parenthood on my behalf.

Someone at the party suggested that next year they hold a Yankee swap version where, rather than simply draw and donate, people may later “steal” causes by agreeing to donate more than the current donor.  However, I thought this might be unfair to those attending who happen to be unemployed or wracking up student debt.  I was wondering if there is an algorithmic-game-theory person out there who could come up with a way to deal with this that might meet the following conditions:

  • the total amount donated is maximized (or at least the price of anarchy is bounded)
  • each person ends up matched to a cause (that is not their own)
  • each person can cap their donation according to their means
  • one’s cap does not hinder the ability to steal a cause
  • the game doesn’t take forever and the rules are simple enough for a smart crowd to understand

I suppose one could hide everything and have causes bid on like Google AdWords, but I think a game of stealing in the spirit of Christmas would be more fun.

nth Combinatorial Potlatch

The Combinatorial Potlatch is a semi-regular (which for last 7 years has been yearly!) one-day workshop in combinatorics held in Cascadia.  It is very informal (no name tags!), very relaxed (only three talks!) and runs on next to no funding*.  The latest installment was this past weekend in Vancouver, BC, held at Simon Fraser University’s downtown campus.

Participants at 2009 Combinatorial Potlatch

I gave a version of my talk on constrained knapsack problems (joint work with Brent Heeringa and Gordon Wilfong).  It was a lot of fun!  The discrete math crowd was fun and patiently sat through my discussions of applications and algorithms and approximations until I finally got to the meat of the talk.  I don’t normally attend discrete math events, but this was a great way to meet people in the area who are graph-minded that I otherwise might not meet.  I also hope that all their best undergraduates will be pointed my way for grad school (hint hint hint).

Louis Deaett (University of Victoria) gave a talk on a (orthogonal) generalization of graph colouring to vector colours where one must assign linearly independent vectors to adjacent vertices while minimizing the dimension of the vectors.  This is certainly not something I had ever dreamt of before.  Only after having let the problem stew for a couple of days am I wondering if a notion can be (or already has been) used in the frequency assignment problem.  Rather than a node transmitting over one frequency, transmit over several; use independence to overcome interference.

Omer Angel (University of British Columbia) spoke on graphs that look the same everywhere from a local perspective.  Given a local pattern centred at a vertex, what kind of graph is such that every vertex has the same local pattern?  Can the graph be finite? Must it be infinite?  For example, if the local pattern is a degree-2 star, then the graph could be a cycle or an infinite path – there is no way of telling which it is.  Certainly, I thought, you could never tell if it is finite or infinite.  Not true.

So, thank you Nancy Ann Neudauer for inviting me, Luis Goddyn for arranging the superb location, and Rob Beezer for quickly correcting that I am a proud beaver, not a duck.

* The host institution provides a room and math-fuel (coffee).

Postdoc after postdoc after postdoc?

There’s talk of postdocking* in the air – for one, Jonathan Katz posted about how to better match recent grads to postdoc positions. It looks like this year’s academic-job market is even worse than last and that postdocs might just fill in the gap for a year or two for some people – including those that are currently postdocking.  Hearing such things make me cringe, but not because I think postdocs shouldn’t exist.  I am very thankful for my 20 months spent as a postdoc.  I don’t think I became a stronger job applicant in that time, but I do think that I became more confident in that time.

In the agonizing months** between interview and job offer at Oregon State University, I gave a lot of thought to “what do I do if I don’t get an academic job?”  I had the option of staying on as a postdoc through summer 2010 – an option that made me cringe.  “If I stay as a postdoc and next year’s market is terrible and then take another postdoc … where does the cycle end?”

I have many friends in the biosciences where two 3+ year postdocs is the norm.  One has started a blog devoted to advocacy for postdocs; a recent post encourages the cycle of postdocing to end.  I worry that CS could “get worse” and end up like bio.  I hope that the competition offered by industry will help keep the postdocking length down.  But Ph.D. enrollment is going up – where are these students supposed to go?  Does anyone know if there are stats on the average postdoc length in computer science?

* I officially propose postdocking as the verbal of postdoc much like trafficking to traffic.
** Days became months due to budget hoop-jumping.

Mathworld v. Wikipedia

I was a mathematics undergraduate in the MathWorld generation.  It spread like wildfire in our department.  I stopped carrying textbooks around with me – instead I could just walk into our undergraduate lab and look something up.  MathWorld was every math textbook I needed.  (A friend of mine was blocked from MathWorld after trying to download all the pages.) We mourned the year MathWorld disappeared.

Unlike my immediate reliance on MathWorld, I have been a slow Wikipedia adopter.  The information on MathWorld seemed more reliable that Wikipedia could ever be, as it is contributed to (exclusively?) by mathematicians.  That said, I can’t imagine Wikipedia going down for a year. (At least, not before the zombie apocalypse starts.)  I find myself more and more using Wikipedia for technical matter.  I don’t think it is solely because I am less likely to look up definitions of groups and more likely to look up definitions of complexity classes.  I think the information on Wikipedia (even for MathWorld-type entries) is richer. Wikipedia entries tend to be more pedagogical than MathWorld’s, handy now that I am teaching.

I still don’t trust Wikipedia, though.  It is a good, quick first reference; a source of examples.  I’m hoping to incorporate Wikipedia participation into my graduate classes once I’ve figured out this teaching thing.  Perhaps I’ll become more trusting of Wikipedia one day, but I wonder if I’ll ever rely on it.

Job talks

I recently found out that when I gave my job talk at Oregon State University last year, I was being recorded.  I was hesitant to post it, but I hope that, despite this far-from-perfect performance, it might be useful to those on the job market this year.  Note that Oregon State is not a theory school.  I was talking to an audience of grad students and faculty, none of whom (except one) work in algorithms.  If I was giving a talk at a theory powerhouse, I probably would have targeted differently.

I broke a lot of standard rules in giving this job talk.  First and foremost, I did not practice it.  *gasp*  Practice would have removed a lot of my “um”s and “uh”s.  In my defence, when I practice a talk too much, I find it gets stale.  However, practicing it once from start-to-finish would have been a good idea.  In watching this talk (as painful as it is), I think the best thing I could have done was to tape myself once.

Second, I climbed on a chair.  I was offered a laser pointer, but I hate laser pointers.  They are hard to keep steady and the point is very small and hard to see for the audience.  I find it about as useful as the speaker pointing to their laptop screen while they give a presentation.  So, at some point I wanted to point at something that too high for me, so I climbed on a chair.

Another minor thing that I wish I would get in the habit of doing is repeating an asked question. Taking two seconds to summarize the question both confirms that you are answering the intended question and allows the entire audience to hear both the question and the answer.

The slides for the talk are available for Keynote and Powerpoint here.

INFORMS on the Smart Grid

I hadn’t heard of the “smart grid” until I arrived in Oregon.  Our department is pushing for a sustainability research collaboration initiative, SENERGI, and so it wasn’t long before I heard our former director, Terri Fiez, talking about the smart grid.  Now, at INFORMS in San Diego, I’m listening to a keynote on the smart grid by Richard O’Neill, the Chief Economic Advisor to the Federal Energy Regulatory Commission

For the unenlightened, the smart grid is the idea of changing the price structure of electricity as well as the appliances that use electricity to manage congestion.  As we move toward more electricity use (i.e. from gas-powered cars, to electricity-powered cars) and electricity generated from renewable and time-constrained resources, congestion could cause more frequent brown-outs than we’ve seen.  Some concrete examples of “smart” include:

  • Appliances equipped to decide when it is best to run: refrigerators that turn off and on to minimize draw on the grid during high-demand hours, dishwashers that wait for low demand hours to run.
  • Batteries equipped to charge by use time: if you arrive home from work in your car (which I’ve been told is possible, but have yet to experience), and plug your electric powered car in along with everyone else who works 9-5, but you don’t need your car again until 6 AM, then the battery will decide to not charge until the middle of the night, perhaps according to some neighbourhood schedule.
  • Batteries used as storage devices on the grid: if you don’t use your car during the week because you do walk or bike or bus to work (congratulations), then the grid could use the battery as a storage device on the grid, charging during low-demand hours and discharging during high-demand.  (Of course, if you don’t need a car during the week, consider not owning a car.  Renting a car almost every weekend is often cheaper than owning a car.)

Of course, for such a system to work, there are significant engineering (after all, even my dishwasher’s simple “delay-start” timer doesn’t work), design and optimization challenges.  The market will become much more complex – will every appliance be considered a player on the market?  Sheesh!  Currently for the (much simpler, I imagine) pricing problems, the cost functions are linearized, which apparently isn’t a great approximation – essentially treating AC current as DC current.  In a system that is worth $10^12/year, a 1% savings is huge news.

I worry though … what if my laptop tells me I can’t write an email at 2AM because I woke up in the middle of the night wracked with algorithmic thoughts because my battery has been discharged so my neighbour can run their washing machine.

How to find a postdoc

While I hardly think I should be doling out advice …

In algorithms, there have been a lot of postdoc positions advertising on the two main email lists, TheoryNT and dmanet.  In my experience, many of the positions are in Europe.  I’ve found that a lot of postdoc’s get their position by word of mouth.

I think, by far, the best thing is to get a postdoctoral fellowship.  Freedom!  It seems NSF doesn’t have a fellowship program for people in computer science.  (Is that actually true?) But I have seen (and ignored, as I am not an American citizen) plenty of postdoc fellowship programs for Americans.  If you aren’t American, try your home country.  NSERC has great fellowships for Canadians that you can take out of the country if you got your Ph.D. in Canada and is tax-free if you take it to McGill.  The short of it is, if you have a fellowship you have the academic freedom to study what you want to study.  You can work with whoever you want, whether or not they have a research grant to pay a postdoc.

I’ve also thought that if you plan far enough in advance you could contact someone you really want to work with and convince them to write a grant with your help that includes funding for a postdoc.  Any thoughts of whether that would work?  I know NSF now asks for an “advising plan” when requesting funds for a postdoc salary.  Would having the potential postdoc involved in the writing process help?

And there are schools and departments that have their own postdoc program – I think U. Penn and U. Toronto do.

Any other suggestions?

What theory should every non-theory Ph.D. student know?

I’ve survived my first week of teaching graduate algorithms and data structures. “Survived” really isn’t the right word. I’ve had a lot of fun and the students in the class are bright and interactive, which makes a 50 minute lecture go by in a flash.

Since the time is going by so quickly, I realize the need to consider more systematically what should be taught in this course. As you might know, I am the only algorithms/TCS person in the department (who isn’t emeritus) and so I will likely be able to quite easily affect the graduate curriculum.  I’m impressed by the amount of theory that the CS Ph.D. students are required to take here (at least in comparison to Brown, a theory-heavy school).  Each student must take the (10-week long) courses called “Algorithms and Data Structures” and “Theory of Computation and Formal Languages”.  Beyond that, there are several other optional algorithms and complexity courses offered every second year.

There has been some discussion on My Biased Coin on what every theory Ph.D. student should know. My question is: given 20 weeks of class time (three 50 minute lectures a week), what topics in TCS should every CS Ph.D. student know?

Feminism is still needed

Many blogs have already piped up on the THE article on the deadly sins of academia (thanks to Gordon Wilfong for first directing me to it).  The article isn’t entirely at fault and meant to be in good fun.  The section on Lust, though, by Terence Kealey, Vice-Chancellor of the University of Buckingham contains such gems that I am sure I need not editorialize:

Normal girls – more interested in abs than in labs, more interested in pecs than specs, more interested in triceps than tripos – will abjure their lecturers for the company of their peers, but nonetheless, most male lecturers know that, most years, there will be a girl in class who flashes her admiration and who asks for advice on her essays. What to do?

Enjoy her! She’s a perk.

I would like to point out, though, the language he uses in his rant:

[T]he universities are where the male scholars and the female acolytes are. […] The fault lies with the females. The myth is that an affair between a student and her academic lover represents an abuse of his power.

While I haven’t personally crossed paths with such overt comments as by Kealy (I have come very close though), the stereotype that men are thinkers and women are not still exists.  Feminism advocates equal rights and equal opportunities for women.  It is our responsibility to create an academic environment that is welcoming to all people, regardless of race, gender or economic means.