Types of Depth and Formula Size

K Kalorkoti

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We use a rank-based measure on rational expressions in indeterminates over a eld and dene 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).
Original languageEnglish
Article number1450031
Number of pages11
JournalAsian-European Journal of Mathematics
DOIs
Publication statusPublished - Jun 2014

Fingerprint

Dive into the research topics of 'Types of Depth and Formula Size'. Together they form a unique fingerprint.

Cite this