University of Maryland Job Posting Mentions Quantum Computing explicitly!

The University of Maryland at College Park has its job posting up (its been up for a while). You can look at it here. I It lists THREE areas but says that they will take applicants from any area. This is believable since they only listed three. Had they listed (say) seven then I would not believe they are looking at other areas. What is the X such that if they list X then you believe they will take from other areas but if you list X+1 then you don't?

The three areas listed are:

1. Cybersecurity
2. Quantum Computing
3. Natural Lang. Proc.

All three of these seem more particular than I usually see in job postings. That is, I've seen things like  Systems, Theory, AI. SO- is this unusual? I don't quite know--- I haven't been on the market for a long time.

Science and Humanities

David Hollinger, a historian, wrote a recent Chronicle Review article The Wedge Driving Academe's Two Families Apart: Can STEM and the human sciences get along?, one of a number of articles I see talking about the connections between science and humanities and the future of humanities at universities.

Most scientists do find great value in the humanities and I would hope vice-versa. But when funds get tight, different fields talk about their relative importance--it happens between science and humanities broadly, it happens between theory and systems in CS departments with limited slots to hire.

I feel badly for humanities these days. In a tight job market, students and parents think hard about doing a humanities major while universities are trying to find ways to cut costs. I don't have a solution--right now the job market calls for more computer scientists than English majors, but I would hate to see an intellectual core of our academic world shrink away.

Humanities are cheap. A provost once said to me it costs the same to hire five philosophers as one physicist once start-up costs and salary are considered. We should find a way to keep funding the humanities while maintaining the strengths across all fields.

Pushing the bounds of human wisdom is important, whether it be in chemistry or classics. Only when we push in all directions does the ball of knowledge truly expand.

Teaching without a net

As a grad student I was teaching the linear-time Median finding algorithm and I FORGOT
that I needed to solve the more general problem of selection. After less than a minute
of trying to see what was wrong I told them

I am sure that Median IS in linear time. I will consult sources  and redo this tomorrow.

I then did the rest of the lecture (which didn't require knowing the Algorithm for Median) and the next day I did the linear Median Finding Algorithm correctly.

Note that I was teaching well known material. So I KNEW that what I was saying was true even if I couldn't  prove it. I also KNOW that I could look it up. I was TEACHING WITH A NET.

When I taught Grad Algs a few years ago I sometimes didn't quite know how the PROOF went  BUT I knew that the STATEMENTS I made were correct, and the algorithms and proofs were out there. In one case I emailed the original author with a subtle point I was stuck on. (It really was subtle- the author himself had to think about it). TEACHING WITH A NET

Last semester some of my Ramsey Theory course was taught WITHOUT A NET. Not in termsof the statements of theorems, but in my attempt to find easier proofs of theorems--- sometimes my alleged proof DID NOT WORK. And there was no book I could consult, nor person I could ask, to help me out on these new ``proofs''. One of my attempted simplifications (of the Canonical Ramsey Theory) DID NOT pan out in the end.

This semester  I am teaching an honors interdisplinary course on Fair Division (nicknamed 'Cake cutting'). I've pulled material from a  variety of different subfields (math, CS, AI. Yes AI!). So I have put some things together that are ``new''(not worth-publishing-new but new in some sense). Some of them have been wrong, or to be more fair, not quite right. But WHO CAN I ASK? Nobody! This is truely teaching WITHOUT A NET. I have made about 2 incorrect statements (both of which were prefaced with `this might not be quite right') but the bigger effect is that every day I wonder if what I am saying is correct.
The effect on the actual course is mininal-- but my mentality going in ``will I make a mistake today that I cannot recover from'' is... interesting.

What to do if you are wrong? Own up to it ASAP. Every minute you fumble around you lose the classes interest.

Is the course working? I think so-- they are learning and having fun. It helps that they are honors students who chose to take this course.

2013 Fall Jobs Post

Time again for the annual fall jobs post. As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out the postdoc and other opportunities on the Theory Announcements site and the Intractability Center. It never hurts to check out the webpages of departments or to contact people to see if positions are available.

I encourage everyone who has a job to offer in theoretical computer science at any level to post links in the comments.

Faculty hiring has rebounded nicely and with computer science enrollments expanding, it should continue to be quite robust. Postdocs will still be down from a few years ago.

Good luck to everyone in the market. I look forward to seeing your names in the 2014 spring jobs post.

Who controls what is taught- the dept or the students?

There is a debate about the questions:

To what extent do we give them what they NEED?  what they WANT?


These questions permeate many other discussions of education.

Rather than discuss this profound issue I will discuss a fictional example.

1. A dept offers one section of Operating Systems (henceforth OS) in the fall and one section in the spring.
2. The same dept also offers one section of AI (henceforth AI) in the fall and one section in the spring.
3. They notice after a few years that the OS tends to underfill and the AI course tends to overfill.
4. Hence they switch to offering OS in the Spring only, and  AI is offered two in the fall and one in the spring.
5. Over time more students take AI and less take OS. Some of this is interest but some is that AI is easier to fit into a schedule since its always offered and has two sections in the spring.
6.  All of the teachers are excellent (remember this is fictional) so the quality of teaching is not the issue. The courses are of equal difficulty so this is not the issue. The courses have the same prerequisites so this is no the issue.
7. The next hiring season they decide to hire someone in AI since they need the teaching help.

The department DID NOT  mean to send the message:

AI is more important than OS.

NOR  did they mean to send the message

 We will let the students decide what is important.

  But the department ended up sending both messages. What should the dept have done? For one they should DECIDE if this is okay with them--- is AI more important than OS? Or more directly, is it okay that students graduate without having a course in OS as  long as they've had a course in AI? They may decide YES- and that would be fine. If they decide NO they could restructure the requirements OR have the advisers give that advice OR just offer less sections of AI.

Does your department fall into this trap--- ending up giving  student's opinions more sway then you intend? 

Shut Down

The NSF core proposal in theoretical computer science, or Algorithmic Foundations as the NSF calls it, has three deadlines this academic year:

• Medium proposals ($500k-$1.2m): October 15
• Large proposals ($1.2m-$3m): November 19
• Small proposals ($0-$500k): January 17

For the most part nearly every core program in computer science has the same deadlines, making it quite an interesting time in CS departments when most of the faculty are all submitting their proposals last minute in January.

Let's talk not about January but about October 15, next Tuesday. Good luck trying to download the proposal call for algorithmic foundations, or the NSF grant proposal guide, or submitting your proposal on Fastlane. All NSF links take you here, where you can read all about what is not happening at the NSF during the government shutdown. So what about October 15?

Once normal operations resume, NSF will issue guidance regarding any funding opportunities that have a deadline or target date that occurs during the government shutdown. Such information will be disseminated via a FastLane Advisory and other electronic methods.

In principle, the government could reopen for business Tuesday morning and the proposals would still be due Tuesday 5 PM. I would guess the deadline would be extended but there is nobody to ask, no one at the NSF to answer the phones and NSF employees are forbidden from responding to or even reading email. At least those that already have grants can keep spending their money, most importantly continuing to fund their students.

These are short term problems, the government will re-open at some point and the NSF will get back to business. But all discussions seem to lead to budget cutting and even just erasing the sequester of last year seems unlikely. The budget crises hasn't stopped Eric Cantor and Lamar Smith from continuing to trash some NSF grants.

Science is too important to be a pawn in politics. Investments in science have given incredible value back to America in terms of jobs and economic growth. Yet somehow science never gets mentioned as a tragedy in the Washington money battles.

P vs NP is Elementary? No-- P vs NP is ON Elementary

As I am sure you all know, the TV show Elementary  (Premise- Sherlock Homes in Modern Day NY. He emails and Texts!  Watson is a female! and...) had an episode that involved P vs NP in a big way. I think they would have been better off with a fictional problem (Bourbaki's conjecture in Recursive Algebraic Topology?) rather than a real problem that they could say rather odd things about.

1. Sherlock Holmes doesn't know what the Mill. Prizes are. I thought most educated people did. Everyone I know knows about them. Could be the company I keep.
2. The show indicates that `Solving P vs NP' means `showing P=NP' It never seems to dawn on them that maybe P is NOT NP.  
3. The show  assumes that once P=NP is proven it will take a very short time to write a program to  use it.  If P=NP is true then I suspect taking the proof and making it work on real world problems would take several years.
4. The show focuses on P=NP's implications for crypto. As Lance has pointed out in his book if P=NP then the benefits for society are GINORMOUS, and would dwarf the relatively minor problem of having to switch to private key  (I agree with Lance for the long term, but I think the short term would be chaotic for security).
5. The show refers to seven Mill problems. While this is technically correct they really should mention that one of them (Poincare's conj.) was already solved. 
6. They seem to think that algebraic geom would be used on P vs NP. If they were claiming it was being use to prove P NE NP then I would think of the Geometric Complexity Theory Program and be impressed. Since they were using it to work on P=NP I'm less impressed. If Alg Geom really is used to prove P=NP then I'll be impressed.
7. How was the episode- I am a fan of the show in general, and this was a solid but not outstanding episode. I wonder if I knew less about P vs NP would I enjoy it more.
8. They are talking about P vs NP on National TV! That's kind-of nice. Only danger is the overhype. If  P NE NP is shown and this has no real world applications then the public may be confused.  I suspect we won't have to worry about that for at least 300 years.

Celebrating Maths in Oxford

This week I'm in Oxford for the opening of the new Andrew Wiles Mathematical Institute building and the Clay Research Conference including on workshop on New Insights on Computational Intractability.

The building is beautiful with two small towers, one each for pure and applied math, and a common room joining them. The downstairs, where the talks are being held, is separated from the tower by its own glass dome, so, I was told, that the noise of the students don't disturb the great thinkers above.

The Clay Math Institute, best known in our circles for the millenium prize problems, has moved to Oxford from Cambridge (Massachusetts) and will take up residence in this new building. Unlike Jim Simons, Landon Clay didn't have a particular math background but was looking for a purpose for a charitable foundation. He met Andrew Wiles and loved the story of his proof of Fermat's last theorem and Clay realized the need for basic math research. Besides the millenium problems, the institute sponsors a number of research fellows and the move to Oxford reflects a transition to funding American mathematicians to a more international base.

What about the new insights into intractability? Lots of great talks on connections to physics and economics, on proof complexity, information theory, algebraic and circuit complexity. On the other hand I watched some talks on other millenium prizes and while difficult to follow, it looks like they have measured progress towards resolving their problems. In complexity, we're still searching for that true path towards P ≠ NP.