Glencora Borradaile






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

March 28, 2014

The difference between a hole and a handle

Filed under: Silent Glen Speaks @ 10:12 pm
Tags:

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.

different-non-separating-cycles-on-surface

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 http://www.math.oregonstate.edu/. Candidates should apply online at http://oregonstate.edu/jobs/, job# 0011757. For full consideration apply by March 1, 2014. Please email all inquiries to the search committee chair, Dr. Julia Jones at julia.jones@oregonstate.edu. 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.

Corvallis_plot_min_max

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 https://womenintheory.wordpress.com/ or contact  womenintheory2014@gmail.com.  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
Tags:

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.

November 1, 2013

TSP in 1-planar graphs

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

I recently came back from a Dagstuhl I organized with Phil, Claire and Daniel on optimization algorithms for planar graphs.  I think I finally caught up for the week away and sat down this afternoon to think about research.  A problem suggested at the workshop was TSP in 1-planar graphs.  1-planar graphs are those graphs that can be drawn in the plane such that any edge has at most one other edge crossing it.

We have PTASes for TSP in bounded-genus graphs and in particular, these PTASes solve the subset TSP problem wherein you want to find the shortest tour that visits an input subset of vertices.  In general graphs, we would just take the metric completion (create the complete graph on that input subset of vertices where the weight of each edge is the length of the shortest path in the original graph) and solve the problem in that completion.  In planar graphs you could do this, but you would lose planarity.  The subset version is inherently interesting: if you are designing a delivery route, you definitely don’t want to visit every intersection in your region.

One would suppose that for 1-planar graphs, one would also want to give a PTAS for the subset version of the problem.  However, we can argue that isn’t the case.  Take a general graph G and consider any drawing of that graph in the plane.  An edge in this drawing will have any number of other edges crossing it, creating a sequence of crossing points along the edge.  Subdivide this edge by introducing a vertex between every consecutive crossing point and distribute the weight of the original edge among these new edges.  Now you have a 1-planar graph H.  If you could find a (1+eps)-approximate tour that visits the subset of vertices that correspond to the vertices of G, this ordering of vertices would correspond to a (1+eps)-approximate tour in G.  However, metric TSP is APX-hard.  So, there can’t be a PTAS for subset TSP in 1-planar graphs.

There might still be a PTAS for TSP (visiting all the vertices) in 1-planar graphs.  This doesn’t seem as interesting a problem though.

« Previous PageNext Page »

© 2015 Glencora Borradaile   Powered by WordPress MU    Hosted by blogs.oregonstate.edu