How can you argue that your leading publication venue is important?
I have been told by our head of department that those on the promotions panel will never have heard of FOCS, STOC and SODA and so this will just be compared with the number papers people publish in any other venue.


I find this stance outrageous.  It is the promotion committee's responsibility to understand—at least at a high level—the publication landscape in the fields in which candidates publish.  Moreover, if the committee is outside your department, it is your department chair's responsibility to educate the committee on the publication culture in your field.

Aside from the conference rankings that Henry mentions, there are other less official rankings of CS departments or just theory groups, based on publication output weighted by prestige.  (The rankings themselves should not be taken seriously, but they do provide a window on what the community thinks of the conferences.)

Another method that might be helpful is to gather evidence about where strong theoreticians actually publish.  Select a handful of successful theoretical computer scientists in top CS departments and show the committee where those people publish.  To pick out a few random DBLP pages off the top of my head: Avrim Blum, Chandra Chekuri, Satish Rao, Santosh Vempala.  Choose whatever experts you consider to be your aspirational peers in your subsubfield.

Alternatively, bypass the "prestige" question and argue directly that your work is strong.  I assume you are provide the review committee with a research statement.  That statement should provide direct evidence that your work is important, visible, and highly regarded.  How often is your work cited, and by whom? (Only your subsubsubfield, or a broader set of researchers?)  What followup work has it inspired by other researchers?  What do other people's papers say about your work or the problems it addresses?  Have you received any research awards (for example, Best Papers or an NSF CAREER) or more indirect accolades (for example, invitations to program committees, journal editorial boards, or Dagstuhl workshops)?  Are you in Oded Goldreich's list, or in David Eppstein's annual top 10?

I'd also recommend asking your department head whether the pre-letter evaluation is merely a sanity check, or if it has real teeth.  My university's promotion process includes a preliminary stage, where the Promotions and Tenure Committee decides whether to request recommendation letters, or not to put the case forward at all.  But at least for tenure cases, this stage is essentially pro forma; a decision not to request letters requires a compelling case for failure.

If that's not the case at your institution, I'd strongly recommend pointing the committee to CRA's Best Practice Memo on Evaluating Computer Scientists and Engineers For Promotion and Tenure.  In particular:


  The primary direct means of assessing impact —to document items (a) and (b) above —is by letters of evaluation from peers. Peers understand the contribution as well as its significance.