Here is the final version (as a .tgz ball of a directory containing all files).
They require a pdf (there is a wap.pdf generated using pdflatex from wap.tex).
I've noticed that ps2pdf and dvi2pdf produce pdfs with wrong margins so
they should probably be avoided; pdflatex can't include .ps (or .eps) 
figures so I generated a pdf for the combined_2 figure (contained in 
the directory).  If there are no further changes, we can just submit
the pdf file in the directory.

I made the following modifications:

- removed the frequent subheadings (the instructions explicitly ask
to avoid them, and so does the first reviewer).

- made the substitution 
	"subset classification" -> "multi-label classification".

- made it explicit that the OAA transformation bound is not new by adding:
  
  The bound in the theorem below is known
  \cite{ASS,Guruswami}, but the analysis we present here is
  instructive because it reveals the assymetry that we later exploit
  in the Weighted One Against All reduction.

- made explicit the dependence of w_0 and w_1 on k in Algorithm 3
  by defining w_i = w_i(k) = BLA instead of w_ki as suggested by 
  reviewer 2. 

I don't have fax access right now and my online access is pretty
pathetic (still visiting my parents).  Could you please submit the pdf
and fax the copyright form (their fax: 650-321-4457)?
They also ask for the form to be mailed via regular mail 
to the following address:

    AAAI Press 
    AAAI-05 Paper Submission 
    445 Burgess Drive 
    Menlo Park, California 94025-3442 
    Telephone: (650) 328-3123 

All instructions are in the acceptance email.
The form is in the AAAI Author Kit: 
http://www.aaai.org/Publications/Templates/AAAI-AuthorKit.zip

Thanks,
Alina