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?
Tag Archives: tcs
TSP in 1-planar graphs
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.
The power of a sysadmin
If you haven’t heard, you must have your head in the sand. And if you haven’t seen the Guardian’s interview of Edward Snowdon, former NSA sysadmin, you should. The actions of one sysadmin could greatly alter this country.
OSU announces new theoretical computer science group!
More exciting news from Oregon State! Mike Rosulek will be joining our faculty in September. Mike will bring some great complexity expertise to our department, but it is for his contributions to the fundamentals of cryptography that we recruited him to OSU. We are building a security group at OSU, and Mike will lead things off. Mike Rosulek graduated from UIUC in 2009 (yes, we are continuing our Illinois love-fest, it seems) and has since been on the faculty at the University of Montana where he has impressively continued and built his research program in secure computation and was awarded an NSF CAREER award.*
For Amir and I, this will mean the start of a real TCS group at OSU. I see seminars and reading groups and generally a more lively theory atmosphere in our future here!
* I think that brings our departmental CAREER count to 21. Given that we have 41 faculty, some of whom were never eligible for CAREER or equivalent, well, that impresses me!
Algorithms group doubles!
I am super happy to announce that Amir Nayyeri will be joining our faculty at Oregon State next year! Amir completed his Ph.D. with Jeff Erickson at UIUC and has been, for the past year, post-doc’ing at CMU with Gary Miller. Amir is an expert in combinatorial optimization in computational topology and geometry. Not only am I excited to work alongside Amir, but our Graphics and Machine Learning groups are also clamoring for more expertise in this area.
As you know, my only complaint about my professional life here has been loneliness. Amir’s joining us will not only make a huge difference to me, but also my graduate students. The two of us, I’m sure, will look forward to recruiting more TCS faculty to join us in the future.
Oh, it’s just so exciting!
What would Aaron Swartz want you to do?
I hadn’t checked my rss-feed reader since the winter break. After the (deserved) attention of the life and untimely death of Aaron Swartz, I was interested in hearing the thoughts of my fellow computer scientists and so delved into the hundreds of unread articles in my rss-feed reader. I was saddened to see that of the 19 personal blogs of computer scientists that I follow, there was only one mention of Aaron Swartz.
Also in the news: driverless cars. Commentators inevitably rave at being able to read a book or watch a movie on the way to work or avoiding those DUII charges. You know what has those features today? Public transit. And you know what doesn’t help to counter the real problem we are increasingly facing, that of overuse of limited resources? Private, individual transportation.
More news: Facebook’s new searching feature, allowing Facebook users to access information that other Facebook users have donated to Facebook in exchange for having up to date information about their friends’ pets and drinking Odysseys. There is a reason why Facebook needed to do this. Facebook has carved out a segment of the web that is proprietary, that only they allow or disallow access to, based necessarily on their profit margin.
As computer science academics we are in a very powerful position. We are trusted with shaping the next generation that will make very important decisions that will have far-reaching social implications. Decisions like those over Facebook’s privacy defaults, motivating technology that enables autonomous private vehicles at the expense of the public interest, defining ownership of electronic media. We make those decisions ourselves in our research; what we research, how we allow our research to be used.
Aaron Swartz cared about this and I think the world would be a better place if we all took action to advance his ideals. We can do so by thinking about our actions. How are you going to get to work today? What are you going to do when you get there? How are you going to choose which problems to focus on? What will you allow your university tech transfer office to do with your IP? What are you going to teach your students, implicitly and explicitly?
Grant writing style questions
This isn’t the most serious question, but when writing a grant (without a co-PI) do you use the royal editorial “we”? Or do your refer to yourself in the first person? When citing your own work, do you use your surname or do you say “the PI”? When writing a grant with more than one person, do you refer to “the PI” and “the co-PI”?
In the grants I’ve read, I’ve seen both. The ones that use “the PI” and “I” generally sound more confident and strong. But there is some discomfort to me in doing so. A little too cocky.
Or tell me to stop quibbling, Cora, and get back to writing.
The $17,500 computer science degree
Update: the tuition for this program has been changed and now amounts to about $30,000. Sadly.
Our department has announced a new, entirely online, bachelor’s degree in computer science which can be completed in one year. Given that we are a public university, this translates to a $17,500 degree*.
I will admit, when I first heard the idea I did not have very good thoughts about it. My negative thoughts included
- one year? yeah right!
- what about programming languages, theory of computation, AI, etc.?
- are we designing ourselves out of jobs? (courses will be administered by non-tenure-track instructors)
- how will standards be maintained?
But then, I got to hear the details. First, it is a post-baccalaureate degree. So, students will already have a bachelor’s degree, and will have need to meet OSU’s post-baccalaureate admissions standards. They will likely be more mature and perhaps working as they study. I’m also glad to see that they are cautioning that completing the degree in one year would be a very intensive, full-time schedule and include two and three-year plans of study. The degree is intended as a second degree, so all optional classes in CS are not mandatory. Of course, this must ruffle some feathers as many courses that are required for graduation in our regular 4-year, first-degree program are not required by this post-bacc degree. (I’m glad algorithms made the cut.) As a post-bacc degree, we will still have the usual cohort of students seeking a CS degree straight out of high-school. Finally, it seems there is a consensus to require 2 proctored exams per course and, at least for the first few years, the assignments and exams will be the same as in the on-site classes.
I’ve been thinking more generally about online classes and online degrees and their social implications. One commenter, pointed out some very valid points of the benefits of online education, that I have to agree with. This degree provides an opportunity for the un- or under-employed to retrain for less than the cost of a new car. The flexible schedule and location of the online classes will allow non-traditional students to study when they can, at the pace that they can. I’m excited to see who will complete this program and from where they study. I’d like to see a concerted effort to recruit women to complete this degree to perhaps counter the gender imbalance in our on-site program.
So, this coming fall, I will be converting my undergraduate algorithms class into an online class in time for a Winter 2013 release. I’m excited to do this** and I’m sure I will have plenty to say about it in the fall.
* ~$15,000 for tuition (in- or out-of-state) plus additional expenses, such as textbooks (~$50 per course), a compatible laptop or computer (~$600), graduation fee ($300) and 2 proctored exams per course (~$30 each).
** And very glad that my department treats this course development as one class-worth of teaching assignment.
*** If you have questions about the program, please contact the program director directly at PostBacCS-online@oregonstate.edu.
crash course in TCS
I recently gave a pair of talks in the Math Department’s Applied Math Seminar on basics of TCS. It was intended for a mathematically mature audience with no background in TCS. The slides for the talk are available here; they are far from perfect — but I will happily take suggestions on things that should be dropped or added. Interest in the talk was pleasantly high. High enough that I plan on doing this again and advertising more broadly — to graduate students in physics, engineering, etc. I also think it acts as a list of topics about which students should be able to answer questions during a comprehensive exam.
Hint. Hint.
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!