Tag Archives: workshop

Women in Theory workshop — applications due February 29

Applications for attendance at the Women in Theory workshop are due February 29.

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.

What I like about this Women in STEM event compared to others is the focus on technical content.  I have been to a number of Women in STEM events and it has, unfortunately, suffered from a “once you’ve been to one you’ve been to them all” feeling.  I wish this workshop had been around in my time.  You may not understand how important it has been to know my fellow female colleagues in theory.  It makes conferences feel much less … sausagey.

I’ll be at the workshop too!  I was invited to speak, and am very excited to be going.  Unfortunately, I’ll have to leave early as I’ll also be starting up the Math/CS REU program at OSU —  applications for that are due today!

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?

Announcement: n-th Annual Combinatorial Potlatch 12/11/10 at Western Washington

Last year I spoke at the n-th Annual Combinatorial Potlatch and had a blast.  The informal workshop is a great idea; I wish there were more regional events like them.  Maybe there are and I just don’t know about them.  The n+1-st Annual Combinatorial Potlatch has been announced – I encourage you to go!

This is the first announcement of the n-th Annual Combinatorial Potlatch, which will be hosted by Western Washington University on Saturday, December 11, 2010 in Bellingham, Washington.

We are close to confirming three speakers for the day’s talks and will soon post a webpage with more details and information that will help you plan your visit.

Main Potlatch Page: http://buzzard.ups.edu/potlatch/index.html

There is no advance registration required, nor any registration fee.  The first talk will be mid to late morning, to allow for travel, followed by a no-host lunch, and two talks later in the afternoon.  Many participants choose to stay for dinner locally.

Combinatorial Potlatches have been held for many years at various locations around Puget Sound and southern British Columbia, and are an opportunity for combinatorialists in the region to gather informally for a day of invited talks and conversation. While most who attend work in, or near, the Puget Sound basin, all are welcome.

Program Committee: Nancy Neudauer, Pacific U
Communications Committee: Rob Beezer, U of Puget Sound
Local Arrangements Committee: Amites Sarkar, Western Washington U

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).