Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any superpolynomial-size lower bound on Frege proofs (in terms of the size of the formula proved) is a major open problem in proof complexity and among a handful of fundamental hardness questions in complexity theory. Noncommutative algebraic formulas, on the other hand, constitute a quite weak computational model, for which exponential-size lower bounds were shown back in 1991 by Nisan [Proceedings of STOC, 1991, pp. 410{418], using a particularly transparent argument. In this work we show that Frege lower bounds in fact follow from size lower bounds on noncommutative formulas computing certain families of polynomials (and that such lower bounds on noncommutative formulas must exist, unless NP = coNP). More precisely, we demonstrate a natural association between tautologies T to families of noncommutative polynomials P such that if T has a polynomial-size Frege proof, then some noncommutative polynomial in P can be computed by a polynomial-size noncommutative algebraic formula, and conversely, when T is a formula in disjunctive normal form, if some polynomial in P has a polynomial-size noncommutative algebraic formula over GF(2), then T has a Frege proof of quasipolynomial size. The argument is a characterization of Frege proofs as noncommutative formulas: we show that the Frege system is (quasi-) polynomially equivalent to a noncommutative ideal proof system(IPS), following the recent work of Grochow and Pitassi [Proceedings of FOCS, 2014, pp. 110{119] that introduced a propositional proof system in which proofs are algebraic circuits and the work in [I. Tzameret, Inform. Comput., 209 (2011), pp. 1269{1292] that considered adding the commutator as an axiom in algebraic propositional proof systems. This also gives a characterization of propositional Frege proofs in terms of (noncommutative) algebraic formulas that is tighter than (the formula version of IPS) in Grochow and Pitassi [Proceedings of FOCS, 2014, pp. 110{119]. [ABSTRACT FROM AUTHOR]