Why Become a Professor

Someone took me to task because in November I posted that the CRA News had 50 pages of job ads but didn't note that very few of those ads specifically were searching for CS theory faculty. Yes, it is true that theory is not as high on the search agenda as big data and other applied areas, but many of these schools will hire theorists after they fail to find qualified applicants in the other areas. My advice is to apply widely and it's not too late to do so, as many CS departments are just starting their interview process.

Why is it so hard for universities to hire in applied CS? Because you are not just competing against other universities, you are competing against industrial labs. Besides the usual arguments of typically hire base salary and no required teaching or grants, a place like Facebook or Google can give you access to data that you just can't get a university and your research will have a real-world impact faster than basic academic research.

So why be a professor? Money isn't as big an issue as you expect, professors can consult, own significant portions of their IP (depending on the school) and can start companies. Teaching is time-consuming but extremely rewarding. To me there are two aspects that make being a professor the best job in the world.

• Freedom to set your own research agenda: Very few labs these days give you the freedom to choose your own research topics and even fewer will reward you for that. In academics we expect you to develop your own research areas and succeed in them. 
• Working with students: The relationship between advisor and advisee is not unlike a parent and child. And there's no better feeling than watching them succeed. You can often get summer interns and postdocs in industry but it just isn't the same.

When is a paper public? When is anything public?

A while back I had a paper in an intermediary stage. The version posted to my Ramsey Theory Course Website was not final. Is the paper public? I didn't think about it much but I didn't intend it to be since it was not done yet. But Adam Sheffer's Google Scholar (more on that later) didn't know that. So his Google Scholar program found the paper and he blogged about it here.

This was FINE- my co-author David Conlon posted a comment on the blog that a revised version was coming, and I asked Adam to modify the blog to say so as well. Plus, I am DELIGHTED and SURPRISED when someone noticed my work.
When the final version came out Adam DID report about it here.
But it raises the question- when is a paper public? Some related thoughts

1. (Kudos to Adam for pointing me to this one). I had heard the ABC conjecture might be solved. What I didn't quite know is that the author posted the papers on HIS OWN website, not on arXiv. Did he intend for it to go public? I do not know- but it is NOW public. If its not correct he can always say well, I didn't tell you it was ready for
   prime time yet.
   
2. A while back a student pointed me to a website with a paper that claimed to show GI is in P. The author DID NOT post it to arXiv (this may have been before there was an arXiv) nor did he email GI experts across the planet to look at it. So is it public? Is it my job to debunk it? It would be a bit odd to tell someone who didn't ask my opinion that YOUR PROOF IS WRONG! The student was hoping it was TRUE so he wouldn't have to learn the proof that if GI is NPC then PH collapses. I ended up telling the student that its surely wrong else since if GI was in P then I would known it--- not a really rigorous proof, but it sufficed. See here for more on this non-rigorous proof technique.
   
3. I have read stories of people who post personal things on FaceBook (a common one is that they are gay) and then are shocked, shocked, when their parents find out.
   
4. There's a nice song about a related issue: My Mom's on Facebook.
   
5. On the TV show West Wing there was a segment where someone thought a story was just regional and hence would not affect her confirmation hearing. She had to be told NO- there is no such thing as a story that is just regional. Journalists and others can FIND STUFF if it is out there.
   
6. Similarly to the last item: I can't post a paper just for my class because Google Scholar will find it (I DO NOT EVER require a password for a course website, I don't want to hassle the students and I am happy if somone else wants to see what I am teaching. Note also that this blog is NOT complaining that Adam found my paper). I (cordially) emailed Adam Sheffer inquiring how Google Scholar found me. For my fellow Luddites I reprint his answer (hmmm, I don't know if he meant his email to be public.)
   

   Regarding how Google Scholar works: The system constantly scans the web for new papers. It knows the papers which I have coauthored (it finds them while searching the web and asks me to verify that they are indeed mine). Then, in future scans, if it stumbles upon a paper that might be relevant to me - it sends me and update about it. I am not sure what exactly are the criteria that it uses, but it seems to be papers by my coauthors and papers on similar topics (perhaps papers that have common references with my papers?).
   

   Sound like when TIVO tried to guess what shows you liked- it could be right but it could be far off. I know of liberals who watched FOX news a lot to gain insight into what people they disagree with thought, and then their TIVO thought were Tea Partiers. Then TIVO thought they liked Tea.
   
7. I gave Adam kindly blogger-to-blogger advice: DO NOT let this be a cautionary tale. Do not ask permission to post about a PAPER --- just do it. I've done it here when blogging about Galois games and here when blogging about how much trig should a governor know. If you post on something a bit more personal (e.g., here) then maybe you should get permission (one of the people gave permission, the other never responded).
   

So what to make of all this? We are in a time of transition and some people
may end up revealing more than they intended. The next generation may learn;
however, we seem to always be in a time of transition.
"p.html" 31L, 4785C written

Analog Adventures

I was 11 forty years ago when Dungeons and Dragons first appeared and by high school many of my friends spent far too many hours embarking on those fantasy adventures. I didn't play much myself only joining a few campaigns for a short period of time. Nevertheless the game hit its mark, giving escapism to our inner nerdoms.

I just finished a new book on D&D Of Dice and Men by David Ewalt. Ewalt tells three interlocking stories: The history of D&D, Ewalt's personal journey into the game, and some campaigns he's embarked on from the characters' point of view.  Gary Gygax and Dave Arneson originally created the game but Dave soon left the company and was written out of the books. Gary mismanaged the company which has bounced around from various owners every since. I hadn't really kept up with D&D after college and I'm surprised that it has so many incompatible versions (reminds me of LaTeX and Python). A fifth version of D&D to unite them all is due for release this summer.

My daughter's school just put on a production of She Kills Monsters, a play about a woman who discovers her late sister through the sister's D&D adventures. My daughter played an evil cheerleader and her line "We're way too powerful for you" reminded us both of her classic role as NP.

These days we have immersive rich interactive games on our Play Stations and smart phones but still there is still nothing like gathering around a table transformed into a tavern as we meet our fellow adventurers and embark on the next quest.

Maryland looking for a Lecturer/Who teachers your intro courses?

My chairman, Samir Khuller, asked me to post our job posting for a lecturer to my blog, so I and doing it right now. I think he overestimates the power of this blog.

At Univ of MD at College Park lecturers teach most sections of our intro sequence (CS1, CS2, CS3, Discrete Math). They might sometimes do a higher level course if the need arises. They are there to mostly teach and advise students, not do research, though some do and that's certainly fine. Some have PhD's and some don't.  Note that this is a full time job--- these are not adjuncts or rent-a-profs. They are part of the department.

Is having lecturers teach the intro courses  a good idea? Overall YES; however, I would like to have professors teaching those courses once in a while, or be involved once in a while, as they may have a good idea to share with the lecturer (then again, they might  not).  Having said that, you don't see me volunteering for CS1, CS2, or CS3 (My policy: I never teach a course where I would get a B if I took it. One exception- I did once teach Graduate Algorithms and got in a bit over my head.) I do teach Discrete Math once in a while. I also like to proofread the midterm and final of whoever is teaching it. I'm NOT that good a proofreader, but I like to know what they are up to and it gives me an excuse to talk to them about the course and make sure it doesn't drift to much. I would like to think I have a good rapport with the lecturers.

Does having a PhD in CS and being a professor give one some insights on what should be in CS1,2,3 and how to teach it? I honestly don't know. My first semester at Univ of MD (1985) we were teaching program verification in CS1. I knew immediately it was a bad idea and eventually (without any input from me) the dept stopped doing that. This is a case where being a researcher may be a negative with regard to education.

I would like to think that my working in theory helps me teach Discrete Math.  It does as a source of some problems (e.g, if a paper says `by an easy induction...' that can be a problem set) but one should not get to carried away and go over their heads.

IEEE and the Conference on Computational Complexity

Dieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a forum to discuss the future affiliation of the conference. Read over the manifesto and update. You can give general comments on the about post. Dieter discusses three options:

1. Remain with IEEE
2. Have a joint ACM/IEEE conference in some fashion.
3. Become an unaffiliated conference.

For most of you this shouldn't matter at all. Most of you readers have never attended the complexity conference (though you ought to give it a try sometime) and those that do would probably continue attending no matter who sponsors the meeting.

There has been a go-it-yourself tendency in this field so as not to pay any organization fees and to publish papers in an open-access format. Just realize this approach has some potential downfalls.

• Without a sponsor, the conference and in particular the organizing committee, is fully responsible for any deficit. One bad hotel contract can sink a conference. To guard against this, you'll need to budget a surplus far larger than IEEE or ACM would require. Also IEEE and ACM can use their influence to get better deals such as on hotels. 
• You'll need considerably more volunteer time from faculty to handle the larger administrative load. This time doesn't show up in the financial calculation but it is a real expense.
• Having a sponsoring organization gives a set of checks and balances to guarantee that the conference retains a consistent mission and be fiscally responsible. If a conference is solo and the organizing committee drops the ball, the conference just disappears. 

I'm not recommendation here, just trying to point out some pitfalls that usually don't get discussed. I'll stay out of the actual debate on the future sponsorship of CCC and leave that to the younger generation.

Superbowl underdogs and overdogs

(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a `big game sale on beer'. I will get around this the same way he does. I hope he doesn't sue.)

In Superb owl XLVIII (48) (one of the few uses of Roman Numerals left) Denver was the favorite but got beaten. This is not so unusual and they were not a favorite by much-just 2.5 points. But they lost 43-8. That sounds unusual--- for the favorite to get completely whomped (spellcheck thinks that's not a word, but spellcheck doesn't even think spellcheck is a word).

So- how uncommon is it for the favorite to get whomped? We would need a rigorous definition of whomped. I'll say two touchdowns, or 14 points. A list of all of the superb owl games and what the spread was and what happened is here. I summarize:

1. The underdog WON 15 times. The most surprising was probably when the NY Jets were an 18-point underdog to the Baltimore Colts  in Supeb owl III in 1969 and won 16-7. Good thing they won since Joe Namath (the NY Jets QB) guaranteed  victory.
2. In 2010, Superb owl 44,  Indianapolis was a 5 points favorite over the New Orleans Saints but the Saints whomped  31-17.
3. In 2003, Superb owl 37,  Tampa Bay was a 4 point underdog to Oakland. Tampa Bay whomped by winning 48-21.'
4. In 1988, Supeb owl 22, Washington was a 3 point underdog to Denver, but Washington whomped 42-10.
5. In 1984, Superb owl 18, LA was a 3-point underdog to Washington, but LA whomped 38-9.
6. In 1981, Superb owl 15, Oakland was a 3 point underdog to Philadelphia, but Oakland Whomped 27-10.
7. In 1970, Superb owl 4, Kansas City was a 12 point underdog to Minnesoda, but whomped 23-7.  The reason they were an underdog is that people still though the AFC to be the lesser league and didn't remember that in Superb Owl 3 the AFC won (though didn't whomp).

So the underdog has whomped 5 times. That is FAR MORE than I would have thought. Does this show that underdogs are undervalued? Not sure since if an underdog wins it doesn't matter by how much for the betting, where as if a favorite wins it matters by how much for the point spread.

This may also call into question if point-spread is the best way to express `this teams is that much better than that team'. One issue (though it was NOT an issue in Superb owl 48) is that if a team is behind
then they may use a high-risk high-reward strategy which, if it fails, they lose my a lot. The phrase one may hear is ``the game was closer than the score''.  Note that for baseball they don't do point spreads, they do odds instead. Should Football follow that? What are the PROS and CONS of points spread vs odds?

The cliche is `I watch the game for the commercials' I actually skip the game and watch the `best of superb owl commercials' that come the week before the game.

Favorite Theorems: Connecting in Log Space

We start the favorite theorems with a result that might surprise many is still less than ten years old.

Undirected Connectivity in Log-Space by Omer Reingold (PDF)

Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze. Reingold's algorithm builds an expander graph based on the zig-zag construction in a very clever way that uses very little space to construct and to check that two points connect.

In 1979, Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. My last favorite theorem from 2004 talked about derandomizing space algorithms and before Reingold the best algorithm for s-t connectivity required log^4/3 space. Indepently of Reingold, Vladimir Trifonov gave a O(log n log log n) space algorithm for s-t connectivity, a victim of bad timing.

One neat implication of Reingold's result is a new and simpler characterization of log-space as the set of problems expressible in first-order logic with ordering and symmetric transitive closure.

After Reingold's result we might have expected solutions to a number of related problems but we didn't see much progress.

• Can every randomized log-space algorithm be derandomized in log space?
• Do there exist log-space computable universal traversal sequences? 
• Can we solve directed s-t connectivity better than Savitch? 
• Can we modify Reingold's algorithm to bring log space into NC¹?

Contribute to the Martin Gardner Centennial

Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here.  I left a comment there, but I expand it for this blog entry.

When I got interested in mathematics in high school I went to the public library looking for math books (this was before Al Gore invented the internet). I found some books by Martin Gardner and began reading them. They were just right for the level of math I was on at the time. My very first proof that I read on my own (outside of a class) was in those books- the proof that (in the terminology I use now) a graph is Eulerian iff every vertex has even degree.

I  learned about SOMA cubes (I bought a set and did every puzzle in the book in about 2 days.This is the only evidence that as a kid I was good at math). I learned the unexpected hanging paradox which confused me then (and still does). I learned the hercules-hydra game and other games that go on for a LOOOOOOOOOONG time. They are related to things in logic. I also learned about NIM games which I have used as a starting point for several student projects.

There have been some conferences in his honors, the Gathering-for-Gardner. I had the pleasure of reviewing some of the books from it. (My review is here.) These articles show that while his work was recreational this is not a well defined term- some if relates to very important and deep mathematics, and some deep math has arisen from such problems. The books also have articles about Gardner the Magician.

In  the 2000's some of his books were reprinted and I was asked to review them for my SIGACT News book review column.  I took this opp to do a joint review of several math recreational books. What a delight to reread his books and contrast them to those of his successors. And I STILL learned some math that I didn't know from them. (My review is here.)

Shortly before a column appears I always email the authors-of-books, authors-of-reviews, and publishers a first draft of my column. His publisher told me that he didn't use email (he was in his 90's!) so I postal mailed him my review. He read it, corrected some typos, but otherwise was quite happy with the review. He died a few months later. I was happy to have some contact, albeit short, with the man who helped keep me interested in math in high school and beyond.