We study alqorithms fpr reducing multiclass categorization problems to multiple binary problems, which then are solved by base binary classifiers. We present two main results. First, we consider base binary classifiers as black boxes and analyze worst-case generalization performances of classifiers constructed by various algorithms, including Max-Win, Decision Directed Acyclic Graphs (DDAG), Adaptive Directed Acyclic Graphs (ADAG), and the unifying algorithm based on coding matrix with Hamming decoding of Allwen, Schapire, and Singer, using only elementary probabilistic tools. Many of these bounds are new, and some are much simpler than prevuosly know. In the second result, we focus on algorithms that explicitly use error information of the base classifiers to improve the performance. We give partial answers to the question regarding the power of these methods, i.e., how much improvement one can obtain with error information. On the one hand, using a game-theoretic framwork, we prove the lowerbound on the worst-case generalization errors for any reductions that use error information, On the other hand, we also present a natural randomized multiclass-bimary reduction algorithm that uses no error information and analyze its generalization error bound. The gap between these upper and lower bounds, which depends only on the error distribution among the base classifiers, is the largest benefit one can gain with error information. We give examples where the gaps are small and large.