How can I improve my chance of getting a tenure-track position My job search (for tenure-track Assistant professor in Computer Science) last year failed miserably.  I submitted applications to about 10 US schools (top 30 -- top-100 quality).   In the end, I got only 1 on-campus interview, which I think I did well, but no job offer.

Here is a quick summary of my qualifications:


ABD from a highly reputable university outside US (equivalent to, e.g., Toronto, EPFL)
10 papers, all in top conferences (5 first-authors)
4 recommendation letters (one from my advisor, 3 from other reputable researchers)
extensive internships in industry research labs
extensive TA experience
has experience in grant-writing (assisting my advisor)


I am really confident in my research accomplishments and research abilities. I also communicate reasonably well and speak/write English fluently.  Since I didn't get a whole lot useful feedback, what do you think are major holes in my profile?  I did some reflections and had the following in mind:


No Post-doc experience (is it really necessary in CS now?)
Never taught a course as an instructor (but I don't see many candidates have this in their resumes)
Degrees not from US
10 papers in top venues are still not enough
Research/Teaching Statement could be written better (perhaps, but I think mine read OK)


Thanks in advance for your suggestions.
Let me add two points to user3188445's excellent answer.

Landing a tenure-track faculty position in computer science, even during this current phase of rampant uncontrolled growth, is still very very hard.  As  user3188445 put it: There's just a lot of randomness in the hiring process.  In this respect, hiring junior faculty is no different from every inherently subjective selection process: undergraduate admission, graduate admission, paper acceptance, senior hiring, even tenure.

There is nothing you can do to absolutely guarantee that the dice fall in your favor, but you can change the distribution.  As one of my interviewers once said to me when I was looking for faculty positions, the variance is a function of the committee, but the expectation is a function of the applicant.

Apply widely


  I submitted applications to about 10 US schools


There's your biggest problem.  Only the very strongest PhD students have any chance of landing a tenure-track job with only 10 applications.  Each position receives dozens to hundreds of applicants; simple statistics imply that you should aim for a wider range of targets.  I'd suggest 40-50 as a more reasonable target.

Hiring protocols vary significantly between American universities.  Some departments practice targeted hiring, where every interview candidate must match a specific research area approved in advance by the dean.  Other departments practice broad-spectrum hiring; these departments can interview anyone they find sufficiently interesting, regardless of area.  Most departments lie somewhere in between these two extremes.  Restrictions can change during the hiring season.  Moreover, the position advertisement does not reveal the department's hiring constraints, or even necessarily preferences.  Some departments publish general ads ("all areas of computer science") even when their searches are targeted; others publish targeted ads even when their searches are broad.

In short, you cannot tell whether your application is in scope for a particular department from the advertisement.  For this reason, you should apply to every department that you might be interested in joining, no matter what their ad says.  The worst they can do is say no.

Quality > Quantity

My second point is one about perception and language: Your entire application package (including the identities of your references and their contents of their letters) should emphasize quality rather than quantity, impact rather than effort, excellence rather than busy-ness.  Even your own internal mental gauges should be calibrated to the strength and potential of your research, not the length of your CV. 

At least one of the metrics we use to choose interview candidates is the question "Is this person likely to get tenure?"  The more you present yourself as someone who is already ready for tenure, the more your achievements shine on the metrics faculty use to judge each other, the better your chances will be.


  ABD from a highly reputable university outside US (equivalent to, e.g., Toronto, EPFL)


The number of non-American CS departments that your prospective American colleagues would rank in the same equivalence class as Toronto and EPFL is very small.  Are you sure?  Are you sure because Americans have told you so, or only because that's what everyone at your home institution says?

In any case, the reputation of your home institution is not as important as your personal reputation as a researcher.  (These are strongly correlated, but they are not the same.)


  10 papers, all in top conferences (5 first-authors)


That's certainly above-average productivity, but productivity is not the same as impact. Did your papers win awards?  Did they create any buzz?  Have they been cited?  Did they inspire follow-up work?  In short, were your papers actually good?  Sturgeon's Law applies even at the best conferences.  Do your external letters (see below) describe the novelty, quality, and impact of your work in specific and credible detail?  Are you, personally, known for this work, as opposed to your advisor?


  4 recommendation letters (one from my advisor, 3 from other reputable researchers)


"Reputable researchers" is too low a bar.  You need letters from recognized intellectual leaders in your field, including a significant fraction from outside your home institution.  As user3188445 points out, you especially need letters from people who are calibrated to the social norms (as some put it, "gushing") of American academic recommendation letters.

It's also important to have American references so that they can give you direct and brutally honest feedback about your application package from the point of view of your target audience.


  extensive internships in industry research labs


Were your internships successful?  Did they lead to publishable or patentable results?  Did they have significant impact within the company?  Did your internship sponsors write you strong recommendation letters?


  extensive TA experience


Unless you are aiming for undergraduate-only institutions or a teaching-only position, this is at most of secondary importance.  Your research matters first.


  experience in grant-writing (assisting my advisor)


Was the grant-writing experience successful?  Did you and your advisor actually get the grant(s)?