Types of depth and formula size
Kyriakos Kalorkoti · Asian-European Journal of Mathematics · 2014
We use a rank-based measure on rational expressions in indeterminates over a field and define notions of size and depth with associated subparts of formulae for expressions. Formulae are allowed to have as inputs expressions from a large set rather than just constants and indeterminates. A general lower bound is derived and this is used to deduce an exponential lower bound, subject to depth assumptions, on the formula size of the determinant with inputs restricted to the usual constants and indeterminates. The general bound is also used to show that a polynomial which is closely related to the determinant has exponential formula size if either (i) some types of operations do not occur in the formula or (ii) some assumptions on depth hold (the inputs allowed here are from a large set).