Abstract.We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are:To such a sequence of problems we assign an exponent similarly as for matrix multiplication. For the complexity of the above problems we prove relative lower bounds of the form

KER_n: Compute a basis of the kernel for a givennbynmatrix,OGB_n: Find an invertible matrix that transforms a given symmetricnbynmatrix (quadratic form) into diagonal form,SPR_n: Find a sparse representation of a givennbynmatrix.a M_n - band absolute lower boundsd n^2, whereM_ndenotes the complexity of matrix multiplication anda,b,dare suitably chosen constants. We show that the exponents of the problem sequencesKER, OGB, SPRare the same as the exponent of matrix multiplication. Back

Abstract.The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subsetXinR^mwhereRis a real or algebraically closed field. We define a notion of verification complexity of a (real) prime ideal (in a prime cone) which gives a lower bound on the decision complexity. We exactly determine the verification complexity of some prime ideals of linear type generalizing a result by Winograd (1970). As an application we show uniform optimality with respect to the number of multiplications and divisions needed for two algorithms:Back

- For deciding whether a number is a zero of several polynomials - if this number and the coefficients of these polynomials are given as input data - evaluation of each polynomial with Horner's rule and then testing the values for zero is optimal.
- For verifying that a vector satisfies a system of linear equations - given the vector and the coefficients of the system as input data - the natural algorithm is optimal.

Abstract.We investigate the complexity of algebraic decision trees deciding membership in a hypersurfaceXin. We prove an optimal lower bound on the number of additions, subtractions and comparisons and an asymptotically optimal lower bound on the number of multiplications, divisions and comparisons that are needed to decide membership in a generic hypersurfaceC^mXin. Over the reals, where in addition to equality branching also <-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfacesC^mXin. In the caseR^mm=1we give also a lower bound for finite subsetsXin. BackR

Abstract.We investigate the impact of randomization on the complexity of deciding membership in a (semi-)algebraic subsetXin. Examples are exhibited, where allowing for a certain error probability in the answer of the algorithms the complexity of decision problems decreases. A randomized decision tree overR^mmwill be defined as a pair(T,u)whereuis a probability measure on someandR^nTis a decision tree overm+n. We prove a general lower bound on the average decision complexity for testing membership in an irreducible algebraic subsetXinand apply it toR^mk-generic complete intersection of polynomials of the same degree, extending results in Buergisser, Lickteig, and Shub (1992), and Buergisser (1992). We also give applications to nongeneric cases, such as graphs of elementary symmetric functions,SL(m,, and determinant varieties, extending results in Lickteig (1990). BackR)

bilinearer Abbildungen

Abstract.We investigate various topics in the area of complexity and deformation theory of bilinear maps and answer some questions posed by V. Strassen in his papers [The asymptotic spectrum of tensors,J. reine angew. Math., 384:102--152] and [Degeneration and complexity of bilinear maps.J. reine angew. Math., 413:127--180].The upper and lower support functionals yield points in the asymptotic spectrum associated with a set of bilinear maps, thus giving necessary conditions for degenerations. We determine the asymptotic growth of the value of the lower support functional on a generic bilinear map of

n-dimensional spaces. We then use this to show that, in contrast to the upper support functional, the lower support functional is not additive.Strassen's theory of asymptotic spectra is based on the discovery that the asymptotic preorder allows an extension from the semiring of equivalence classes of bilinear maps to its Grothendieck ring. We prove that the degeneration order does not allow such an extension.

In the last section, we study a question in the general setting of a linear algebraic group

Goperating on a vector spaceVover a fieldk. For objects inVwe definek-degeneration<_k,k-isomorphy~_k, and isomorphy~(defined with respect to the algebraic closure ofk). We investigate the so-calledstrong partial order property(SPE):d <_kf,d ~ f==>d ~_kf. We prove that (SPE) is always true ifkis algebraically closed, real closed, or ap-adic field. Moreover, we show that (SPE) is true ifGis a torus. We verify (SPE) for the operation ofGl(n,k)on quadratic forms over finite fieldskand over the rationals. Finally, in the setting of bilinear maps, we are able to show that the implication of (SPE) is true for certain direct sums of matrix multiplications. Back

Complete Intersections

Abstract.We study the complexity of algebraic decision trees that decide membership in a semi-algebraic subsetXin, whereR^mRis a real (or algebraically) closed field. We prove a general lower bound on the verification complexity (cf. Lickteig (1990), and Buergisser and Lickteig (1992)) of the vanishing ideal of an irreducible algebraic subsetXinin terms of the degree of transcendency of its minimal field of definition. As an application, we determine exactly the number of additions, subtractions and comparisons that are needed to test membership in a generic complete intersection; for the number of multiplications, divisions and comparisons needed, we obtain an asymptotically optimal lower bound. This generalizes the main results in Buergisser, Lickteig, and Shub (1992). A further application is given to test problems related to partial or continued fractions. BackR^m

of Bilinear Maps

Abstract.We investigate whether Strassen's theory of asymptotic spectra could be simplified by extending the degeneration order into a ring. It turns out that this must necessarily fail. This negative result shows once more the intricacy of bilinear complexity. Along the way, we develop a necessary condition for degenerations in terms of dimensions of isotropy groups of tensors. Back

polynomial ideal membership problem

Abstract.The complexity of the polynomial ideal membership problem over arbitrary fields within the framwork of arithmetic networks is investigated. We prove that the parallel complexity of this problem is single exponential over any infinite field. Our lower bound is obtained by combining a modification of Mayr and Meyer's key construction (1982) with an elementary degree bound. Back

Abstract.In 1979 Valiant developed a nonuniform algebraic analogue of the theory of NP-completeness for computations with polynomials over a field. This theory centers around his hypothesis VP <> VNP, the analogue of Cook's hypothesis P <> NP. We identify the Boolean parts of Valiant's algebraic complexity classes VP and VNP as familiar nonuniform complexity classes. As a consequence, we obtain rather strong evidence for Valiant's hypothesis: if it were wrong, then the nonuniform versions of NC and PH would be equal. In particular, the polynomial hierarchy would collapse to the second level. We show this for fields of characteristic zero and finite fields; in the first case we assume a generalized Riemann hypothesis. The crucial step in our proof is the elimination of constants in the field, which relies on a recent method developed by Koiran (1996). Back

Abstract.In 1979 Valiant developed an algebraic analogue of the theory of NP-completeness for computations of polynomials over a field. We further develop this theory in the spirit of structural complexity and obtain analogues of well-known results by Baker, Gill, and Solovay (1975), Ladner (1975), and Schöning (1982, 1984).

- We show that if Valiant's hypothesis is true, then there is a
p-definable family, which is neitherp-computable nor VNP-complete. More generally, we define the posets ofp-degrees andc-degrees ofp-definable families and prove that any countable poset can embedded in either of them, provided Valiant's hypothesis is true. Moreover, we establish the existence of minimal pairs for VP in VNP.- Over finite fields, we give a
specificexample of a family of polynomials which is neither VNP-complete norp-computable, provided the polynomial hierarchy does not collapse.- We define relativized complexity classes VP^h and VNP^h and construct complete families in these classes. Moreover, we prove that there is a
p-familyhsatisfying VP^h = VNP^h. Back

Abstract.We describe a fast algorithm to evaluate irreducible matrix representations of general linear groups GL(m,C) with respect to a symmetry adapted basis (Gelfand-Tsetlin basis). This is complemented by a lower bound, which shows that our algorithm is optimal up to a factor m^2 with regard to nonscalar complexity. Our algorithm can be used for the fast evaluation of special functions: for instance, we obtain an O(l log l) algorithm to evaluate all associated Legendre functions of degree l. As a further application we obtain an algorithm to evaluate immanants, which is faster than previous algorithms due to Hartmann and Barvinok.

Abstract.Permanents and determinants are special cases of immanants. The latter are polynomial matrix functions defined in terms of the characters of the symmetric groups and corresponding to Young diagrams. Valiant has proved that the evaluation of permanents is a complete problem in both the Turing machine model (#P-completeness) as well as in his algebraic model (VNP-completeness). We show that the evaluation of immanants corresponding to hook diagrams or rectangular diagrams of poynomially growing width is both #P-complete and VNP-complete. Back

Abstract.In the last years the quantitative modelling of credit risk has received a lot of attention within the financial industry. Several models have been released to the public, notablyCreditRisk+, Credit Metrics, Credit Portfolio View[CR97, CM97, CP98]. Although different approaches to credit risk are used, studies have shown that the models yield similar results if the parameters are set in a consistent way, see for example [KO98].CreditRisk+in particular is ideal for practical implementation and has some nice features, namely: (a) few assumptions have to made, (b) the methodology is very transparent and based on concepts already used in the insurance business, and (c) the loss distribution can be calculated analytically in an efficient way using an iterative procedure.One of the shortcomings of the

CreditRisk+model is the assumption of independent sectors. The sectors represent for example different regions or industries within the economy and individual onligors can be assigned to particular sectors. In order to perform a sector analysis, the authors ofCreditRisk+propose apportioning an obligor's systematic risk across a mixture of independent sectors. However, such an approach is difficult to realize in practice.In this paper, we present a framework for extending the

CreditRisk+model by examining correlations between industries and derive a formula for the unexpected loss and risk contributions. The correct modelling of correlations of default risk between sectors is very important for examining the effects of diversification on active portfolio management. Note that only the loss from defaults of counterparties is modelled.The article is organized as follows: we first derive the probability generating function of the loss distribution for one sector following the

CreditRisk+approach. This is then generalized to several sectors to obtain the first two moments of the loss distribution, as well as a loss distribution consistent wiith the observed correlations between sectors. Back

Abstract.We present an approach to model credit risk that incorporates the risk of counterparty default and the risk of devaluation of the collateral. The framework is based on a two-dimensional segmentation by industry and collateral type. The systematic effects in both risk drivers are taken into account by volatilities within, and by correlations between the segments. We derive a simple formula for the variance of the loss distribution and describe an algorithm to compute this distribution. Moreover, we show that in the limit of a large portfolio, the loss distribution directly mirrors the assumptions on the economy and depends on the portfolio structure only through the relative expected loss weights. Back

Decision versus Computation in Algebraic Complexity

Back

Back

Back

Back

Back

Back

Back

Back

Back

Back

Back

However, we prove that by considering $G_s$-representations, as suggested in GCT1-2, only trivial lower bounds on border rank can be shown. It is thus necessary to study $G$-representations, which leads to geometric extension problems that are beyond the scope of the subgroup restriction problems emphasized in GCT1-2. We prove a very modest lower bound on the border rank of matrix multiplication tensors using $G$-representations. This shows at least that the barrier for $G_s$-representations can be overcome. To advance, we suggest the coarser approach to replace the semigroup of representations of a tensor by its moment polytope. We prove first results towards determining the moment polytopes of matrix multiplication and unit tensors. Back

To illustrate the applicability of our results, we also show that computing the quantified star size of a formula is possible in time n

*Author:* P. Buergisser.
*Last change:* July 10, 2013 by C. Ikenmeyer