Glencora Borradaile

         Assistant Professor, School of Electrical Engineering and Computer Science, Oregon State University

April 1, 2014

The ball-coverage property and a great journal turnaround time

Filed under: Silent Glen Speaks @ 7:37 pm

Erin Wolf Chambers and I had a paper accepted yesterday to the journal Discrete & Computational Geometry, a journal I now highly recommend.  This entry is a story about that paper as well as the journal.

In a keynote talk at CanaDAM 2011, Stéphan Thomassé referred to the following theorem of Chepoi, Estellon and Vaxès:

Any planar graph of diameter at most 2R has a subset of O(1) vertices such that every vertex in the graph is within distance R of that subset.

We’ll call this coverage of the graph by O(1) balls of radius R the “ball-coverage property”.  The proof is quite deep in that it calls on the fractional-Helly property of the set system of radius-R balls.  In his talk, Thomassé states that the constant is not computed in the paper, but was done so by a student.  I don’t remember the exact number, but it was around 800.

Surely that can’t be the right number.  I worked for a while on coming up with a different, more direct proof that would result in a better number.  Something reasonable.  Like 5.  Or 7.  The best known lower bound is 4.

I haven’t been successful.  Erin and I, in our first successful collaboration which involved an allergic reaction to St. Louis (actually to a hand cream, not St. Louis), generalized the result to bounded genus graphs.  That is this paper.  We thought we had it generalized to clique sums of surface embedded graphs … we can handle apices, but vortices and clique sums proved … tricky.  As they seem to be.  But I would suggest that minor-excluded graph families have the ball-coverage property.

We had this result written up in the summer and debated where to send it.  SoCG was out as Erin is on the PC this year.  Rather than wait for a spring submission, we decided to go straight for a journal.  We submitted to DCG on October 22, 2013.  We were asked for what turned out to be minor revisions on March 12, 2014 and resubmitted on March 19.  The final acceptance came in on March 31, 2013.  Just over 5 months from first submission to acceptance.

That is comparable to the roughly 3 months for conferences, with the added benefit that you can actually have a back-and-forth as needed with the reviewers through the editor.  No rejections based on misunderstandings.  No rejections based on “we only have X spots”.  No rolling the dice.  And no travel to yet another far away conference.

If only more journals were like this.  If only conferences were more about giving a place for people to meet (regionally as well as internationally) and less about picking the X top papers without a truly full review even though it is treated like a fully published result … well … that would be great.

March 28, 2014

The difference between a hole and a handle

Filed under: Silent Glen Speaks @ 10:12 pm

I have learnt topology in a very haphazard fashion. So sometimes when I observe something for the first time, my mind is blown. Topology is beautiful. Today’s lesson was in the difference between a hole and a handle.


So here’s the example, on the left are two examples of non-separating cycles on an orientable surface of genus 2.  If we cut along them we get two surfaces that are topologically equivalent (right).  To get back to the original surface, we can fill in the holes with disks (red), identify the two disks and then delete the disk.  Call the two disks A and B.  Since the surface on the right is orientable, when the disks are glued into the holes, there are two distinct sides of the disk, the inside and outside.  There are three ways to glue these disks together:
(i) inside of A to inside of B
(ii) outside of A to outside of B
(iii) outside of A to inside of B or inside of A to outside of B
The top example is (i) and the bottom is (ii).  (iii) results in a non-orientable surface.  Even though (i) and (ii) result in the same topological surface, the cycles used are fundamentally different because we have used a geometric idea of inside and outside.  If I were living in the interior of this surface, the holes would look like handles and vice versa.  [mind blowing sounds]  In other words, given an orientable surface and a defined inside and outside a handle is a cycle that you can contract in the inside of the surface, and a hole is a cycle that you can contract in the outside of the surface.

February 10, 2014

Search for new Head of Department of Mathematics at OSU

Filed under: Silent Glen Speaks @ 3:49 pm

via Dean Pantula:

The College of Science of Oregon State University invites applications for the position of Head of the Department of Mathematics, beginning in the Fall of 2014. This is an open search for an outstanding scholar with demonstrated excellence in research, appropriate research grant funding, excellence in teaching, and a strong commitment to educational programs at the undergraduate and graduate level. The successful candidate will have a Ph.D. in Mathematics or a closely related discipline; an established record of scholarship commensurate with the appointment at the rank of full professor with tenure; a commitment to promoting and enhancing diversity; demonstrated abilities in teaching; a commitment to mentoring junior faculty; and demonstrated potential for successful academic leadership to enhance the Department’s excellent research and educational programs, as shown by her or his record of service to the Department, University, and profession. All areas of expertise in mathematics will be considered. Some experience with management responsibilities or administrative roles where strong interpersonal skills were necessary is preferred. The appointment will carry a salary rate commensurate with the duties and responsibilities. Applicants should submit a cover letter which includes a vision statement for the department, curriculum vitae, statements of administrative and teaching philosophies, a research statement, and contact information for five professional references; one of these should address teaching ability. Application materials must show a demonstrable commitment to promoting and enhancing diversity. Oregon State University is an Affirmative Action/Equal Opportunity Employer and is committed to enhancing diversity. Additional information about the Department is available at Candidates should apply online at, job# 0011757. For full consideration apply by March 1, 2014. Please email all inquiries to the search committee chair, Dr. Julia Jones at OSU is an AA/EOE and has a policy of being responsive to dual-career needs.

January 17, 2014

Conversations with graduate students

Filed under: Silent Glen Speaks @ 12:04 am
Tags: , ,

A male graduate student told me he started taking a yoga class only to find that there was only one other man and the remaining 29 were women.  He said he didn’t feel like he belonged and so he dropped the class.

A female graduate student at SODA told me she didn’t see a single talk by a woman and she didn’t feel like she belonged.

(There were talks by women, but with 3-4 sessions, and none of the keynotes by women, well, they can be easy to miss.)

January 13, 2014

Bringing current events into the technical classroom

I spent last summer thinking about how to bring something related to the climate crisis into my fall undergraduate algorithms class.  In this class, I have converged on having 4-5 projects covering iterative, divide and conquer, dynamic programming, linear programming and heuristics.  These projects each have a practical component where an algorithm is implemented.  Linear programming seemed to be the tool that I could use to “solve” some problem in climate change.  It wasn’t until I stumbled upon this article by Robert Vanderbei suggesting an upper-level class project wherein students fit a curve to daily temperature recordings.  The suggested curve is the superposition of

  • a sinusoidal curve with a period of one year to model the change in seasons,
  • a sinusoidal curve with a period of 10.7 years to model the solar cycle, and
  • a linear term representing any drift in mean daily temperatures.

I adapted the suggested project to my class and had them fit such a curve, using GLPK, to 60 years of daily temperature recordings for Corvallis.


I provided the students with the data and offered bonus credit for students who repeated the project for another location (downloading data from NOAA).  The students found the project challenging but seemed to appreciate the tangibility of the project, so I think I will likewise adapt other projects. The students could then interpret the coefficient of the linear term as the amount of warming in average daily temperatures.

A few interesting things came up.  For example, apparently two different versions of GLPK find two different “optimal” solutions to the same LP — with different values.  For more details, please see the project description.

Next year, I think I will have them choose their own location by default as I think it is a useful experience to clean data …

December 19, 2013

School pride in taking a stance on climate change

I can’t help but share my pride in my fellow faculty for taking a strong stance on climate change.  Our university is a leader in climate change research and is now moving toward being a similar leader in climate change policy.  Our faculty senate recently voted to call upon our Foundation (which manages our endowment) to

  1. immediately cease all new investment in any of the top 200 fossil fuel companies;
  2. use its expertise to ensure that within five years none of its assets include holdings in such companies; and
  3. release quarterly updates to the public detailing progress made toward complete divestment.

Of course this is still just the first step and we have to follow through with action from the Foundation.  Although their bottom line is maximum earnings, they have a new process for hearing such requests — a hopeful sign in my mind.

Compare this to the recent decision by (my unfortunate alma mater) Brown’s president to defend their continued investment in the 15 largest coal companies, using (weak) arguments similar to those used to counter divestment from South Africa during the apartheid regime (“We all agree racism is horrible, but this isn’t the right way to oppose it!”). This seems to be the story for climate change.  We all agree it is something to be avoided (or, sadly, simply ‘mitigated’), but we really aren’t doing anything about it.  There’s a lot of talk and little action.

Thankfully, I can be proud of the Brown students who are not giving up.

December 9, 2013

Undergraduate algorithms study guide

A year ago, I was just finishing putting together materials for the new online version of our undergraduate algorithms course.  I’ve finally compiled all that material into one webpage: available here. There are a few things not yet posted, but this is essentially the content of our undergraduate algorithms course less the assignments and exams. As when I teach the on-site course, I relied heavily on material from others, notably:

Though the “interactive questions” were written by me, they were not implemented by me.  I have to thank Oregon State University’s eCampus group for that.

Hopefully this will be helpful to others, though it assumes the particular prerequisites of our program …

December 3, 2013

Women in Theory Workshop: Call for Participation

via Lisa Zhang, Tal Rabin and Shubhangi Saraf:

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.

The 4th WIT workshop will take place at Google New York, May 28 – 30, 2014, in coordination with NYU and Princeton, right before ACM STOC 2014.

Confirmed Speakers: Lenore Blum (CMU), Julia Chuzhoy (TTI), Shafi Goldwasser (MIT), Orna Kupeferman (Hebrew U.), Katrina Ligett (Caltech), Rotem Oshman (U. Toronto), Vera Sos (Alfrd Rnyi Institute of Mathematics).

Important dates:
Application deadline:  January 20,  2014.
Notification of acceptance: February 10,  2014.
Workshop: May 28-30, 2014.

For more information see or contact  I attended WIT as a speaker in 2012 and had a wonderful time.  I wish it was something I could go back to every year!  I highly recommend you encourage your graduate students to go!

December 1, 2013

Mentoring junior faculty — what does your school do?

Filed under: Silent Glen Speaks @ 11:07 pm
Tags: ,

I’ve been charged (with the help of others) with formalizing our junior-faculty mentoring practices.  Rather than reinvent the wheel, I’ve been looking into what other universities do.  It’s a little bit of information overload.  For example, these sites provide a glut of information.  It would be more helpful for me to have case studies — examples of how mentoring is done in various contexts.  So, this is the open question: What does your department do?  What do you wish your department did?

November 7, 2013

Still hiring at OSU: 6 positions open this year

Filed under: Silent Glen Speaks @ 3:25 pm

Have I mentioned that we’re hiring?

The School of Electrical Engineering and Computer Science at Oregon State University invites applications for up to six full-time nine month tenure-track positions at the Assistant Professor level in Computer Science. Appointments may be made at the Associate or Full Professor level. We seek candidates with a commitment to quality teaching and with demonstrated research strengths in the areas of databases, software engineering, computer security, distributed systems, and computer vision.

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.

« Previous PageNext Page »

© 2015 Glencora Borradaile   Powered by WordPress MU    Hosted by