Edinburgh Research Explorer

Types of Depth and Formula Size

Research output: Contribution to journalArticle

Original languageEnglish
Article number1450031
Number of pages11
JournalAsian-European Journal of Mathematics
DOIs
StatePublished - Jun 2014

Abstract

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).

Download statistics

No data available

ID: 15315078