Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication

P. Buergisser, M. Karpinski, and T. Lickteig

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:
  • KER_n: Compute a basis of the kernel for a given n by n matrix,
  • OGB_n: Find an invertible matrix that transforms a given symmetric n by n matrix (quadratic form) into diagonal form,
  • SPR_n: Find a sparse representation of a given n by n matrix.
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 a M_n - b and absolute lower bounds d n^2, where M_n denotes the complexity of matrix multiplication and a,b,d are suitably chosen constants. We show that the exponents of the problem sequences KER, OGB, SPR are the same as the exponent of matrix multiplication. Back

Verification complexity of Linear Prime Ideals

P. Buergisser and T. Lickteig

Abstract. The topic of this paper is the complexity of algebraic decision trees deciding membership in an algebraic subset X in R^m where R is 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:
  • 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.
Back

Test Complexity of Generic Polynomials

P. Buergisser, T. Lickteig, and M. Shub

Abstract. We investigate the complexity of algebraic decision trees deciding membership in a hypersurface X in C^m. 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 hypersurface X in C^m. Over the reals, where in addition to equality branching also <-branching is allowed, we prove an analoguous statement for irreducible ``generic'' hypersurfaces X in R^m. In the case m=1 we give also a lower bound for finite subsets X in R. Back

On Randomized Semi-algebraic Test Complexity

P. Buergisser, M. Karpinski, and T. Lickteig

Abstract. We investigate the impact of randomization on the complexity of deciding membership in a (semi-)algebraic subset X in R^m. 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 over m will be defined as a pair (T,u) where u is a probability measure on some R^n and T is a decision tree over m+n. We prove a general lower bound on the average decision complexity for testing membership in an irreducible algebraic subset X in R^m and apply it to k-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,R), and determinant varieties, extending results in Lickteig (1990). Back

Degenerationsordnung und Tragerfunktional
bilinearer Abbildungen

P. Buergisser

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 G operating on a vector space V over a field k. For objects in V we define k-degeneration <_k, k-isomorphy ~_k, and isomorphy ~ (defined with respect to the algebraic closure of k). We investigate the so-called strong partial order property (SPE): d <_k f, d ~ f ==> d ~_k f . We prove that (SPE) is always true if k is algebraically closed, real closed, or a p-adic field. Moreover, we show that (SPE) is true if G is a torus. We verify (SPE) for the operation of Gl(n,k) on quadratic forms over finite fields k and 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

Decision Complexity of Generic
Complete Intersections

P. Buergisser

Abstract. We study the complexity of algebraic decision trees that decide membership in a semi-algebraic subset X in R^m, where R is 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 subset X in R^m in 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. Back

A Note on the Degeneration Order
of Bilinear Maps

P. Buergisser

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

On the parallel complexity of the
polynomial ideal membership problem

P. Buergisser

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

Cook's versus Valiant's Hypothesis

P. Buergisser

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

On the Structure of Valiant's Complexity Classes

P. Buergisser

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 neither p-computable nor VNP-complete. More generally, we define the posets of p-degrees and c-degrees of p-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 specific example of a family of polynomials which is neither VNP-complete nor p-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-family h satisfying VP^h = VNP^h. Back

The computational complexity to evaluate representations of general linear groups

P. Buergisser

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.

Back

The computational complexity of immanants

P. Buergisser

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

Credit risk models: integrating correlated industries

P. Buergisser, A. Kurth, A. Wagner, and M. Wolf

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, notably CreditRisk+, 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 of CreditRisk+ 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

Incorporating Severity Variations into Credit Risk

P. Buergisser, A. Kurth and A. Wagner

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

The Complexity of Factors of Multivariate Polynomials

P. Buergisser

The existence of string functions, which are not polynomial time computable, but whose graph is checkable in polynomial time, is a basic assumption in cryptography. We prove that in the framework of algebraic complexity, there are no such families of polynomial functions of p-bounded degree over fields of characteristic zero. The proof relies on a polynomial upper bound on the approximative complexity of a factor g of a polynomial f in terms of the (approximative) complexity of f and the degree of the factor g. This extends a result by Kaltofen (STOC 1986). The concept of approximative complexity allows to cope with the case that a factor has an exponential multiplicity, by using a perturbation argument. Our result extends to randomized (two-sided error) decision complexity. Back

On Implications between P-NP-Hypotheses:
Decision versus Computation in Algebraic Complexity

P. Buergisser

Several models of NP-completeness in an algebraic framework of computation have been proposed in the past, each of them hinging on a fundamental hypothesis of type P$\ne$NP. We first survey some known implications between such hypotheses and then describe attempts to establish further connections. This leads us to the problem of relating the complexity of computational and decisional tasks and naturally raises the question about the connection of the complexity of a polynomial with those of its factors. After reviewing what is known with this respect, we discuss a new result involving a concept of approximative complexity. Back

Lower Bounds and Real Algebraic Geometry

P. Buergisser

Many relevant problems in symbolic computation and computational geometry can be formalized as semi-algebraic computation or decision problems, to be solved by means of algebraic computation trees. It is a general paradigm that a complicated geometrical, topological, or combinatorial structure of a problem should result in high computational complexity. This survey outlines some of the ideas leading to lower bounds in terms of degree, Betti numbers, and number of faces of an arrangement or a polyhedron, emphasizing the role of real algebraic geometry in this endeavour. The impact of randomization on decision complexity is briefly discussed. Back

Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps

P. Buergisser and M. Lotz

We prove lower bounds of order n\log n for both the problem of multiplying polynomials of degree n, and of dividing polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [Proc.\ 34th STOC 2002] proposed for matrix multiplication. It reduces the linear problem of multiplying a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [J.\ ACM 20, pp.\ 305-306, 1973] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix. In addition, we extend these lower bounds for linear and bilinear maps to a model of circuits that allows a restricted number of unbounded scalar multiplications. Back

On the Algebraic Complexity of some Families of Coloured Tutte Polynomials

M. Lotz and J.A. Makowsky

We investigate the coloured Tutte polynomial in Valiant's algebraic framework of NP-completeness. Generalising the well known relationship between the Tutte polynomial and the partition function from the Ising model, we establish a reduction from the permanent to the coloured Tutte polynomial, thus showing that its evaluation is a VNP-complete problem. Back

Counting Complexity Classes for Numeric Computations I: Semilinear Sets

P. Bürgisser and F. Cucker

We define a counting class #P_add in the BSS-setting of additive computations over the reals. Structural properties of this class are studied including a characterization in terms of the classical counting class #P introduced by Valiant. We also establish transfer theorems for both directions between the real additive and the discrete setting. Then we characterize in terms of completeness results the complexity to compute basic topological invariants of semi-linear sets given by additive circuits. It turns out that the computation of the Euler characteristic is FP_add^{#P_add}-complete, while for fixed k, the computation of the kth Betti number is FPAR_add-complete. Thus the latter is more difficult under standard complexity theoretic assumptions. We use all the above to prove some completeness results in the classical setting. Back

Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets>

Peter Bürgisser and Felipe Cucker

We define counting classes #P_R and #P_C in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over R, or of systems of polynomial equalities over C, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over R) and algebraic sets (over C). We prove that the problem to compute the Euler characteristic of semialgebraic sets is FP_R^{#P_R}-complete, and that the problem to compute the geometric degree of complex algebraic sets is FP_C^{#P_C}-complete. We also define new counting complexity classes in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving , for all k in N, the FPSPACE-hardness of the problem of computing the kth Betti number of the set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology. Back

Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré

Peter Bürgisser and Felipe Cucker

This paper surveys some connections between geometry and complexity. A main role is played by some quantities - degree, Euler characteristic, Betti numbers - associated to algebraic or semialgebraic sets. This role is twofold. On the one hand, lower bounds on the deterministic time (sequential and parallel) necessary to decide a set S are established as functions of these quantities associated to S. The optimality of some algorithms is obtained as a consequence. On the other hand, the computation of these quantities gives rise to problems which turn out to be hard (or complete) in different complexity classes. These two kind of results thus turn the quantities above into measures of complexity in two quite different ways. Back

The Complexity to Compute the Euler Characteristic of Complex Varieties

Peter Bürgisser, Felipe Cucker, and Martin Lotz

Back

Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets

Peter Bürgisser, Felipe Cucker, and Martin Lotz

In [Bürgisser & Cucker 2004a] counting complexity classes #P_R and #P_C in the Blum-Shub-Smale setting of computations over the real and complex numbers, respectively, were introduced. One of the main results of [Bürgisser & Cucker 2004a] is that the problem to compute the Euler characteristic of a semialgebraic set is complete in the class FP_R^#P_R. In this paper, we prove that the corresponding result is true over C, namely that the computation of the Euler characteristic of an affine or projective complex variety is complete in the class FP_C^#P_C. We also obtain a corresponding completeness result for the Turing model. Back

The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties

Peter Bürgisser and Martin Lotz

We continue the study of counting complexity begun in [Buergisser, Cucker, Lotz 04] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in [Bach 99]. Back

The complexity of semilinear problems in succint representation

Peter Bürgisser, Felipe Cucker, and Paulin Jacobé de Naurois

We prove completeness results for twenty three problems in semilinear geometry. These results involve semilinear sets given by additive circuits as input data. If arbitrary real constants are allowed in the circuit, the completeness results are for the Blum-Shub-Smale additive model of computation. If, in contrast, the circuit is constant-free, then the completeness results are for the Turing model of computation. One such result, the P^NP[log]-completeness of deciding Zariski irreducibility, exhibits for the first time a problem with a geometric nature complete in this class. Back

On the Complexity of Numerical Analysis

E. Allender, Peter Bürgisser, J. Kjeldgaard-Pedersen, and P. Miltersen

We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the following problem, which we call PosSLP: Given a division-free straight-line program producing an integer N, decide whether N>0. We show that PosSLP lies in the counting hierarchy, and we show that if A is any language in the Boolean part of P_R accepted by a machine whose machine constants are algebraic real numbers, then A \in P^{PosSLP}. Combining our results with work of Tiwari, we show that the Euclidean Traveling Salesman Problem lies in the counting hierarchy -- the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.
Back

Exotic quantifiers, complexity classes, and complete problems

Peter Bürgisser and Felipe Cucker

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda in doing so is twofold. On the one hand, we show that a number of problems whose precise complexity was previously unknown are complete in some of the newly defined classes. This substancially expands the catalog of complete problems in the BSS theory over the reals thus adding evidence to its appropriateness as a tool for understanding of the complexity of numeric computations. On the other hand, we show that some of our newly defined quantifiers have a natural meaning in complexity theoretical terms. An additional profit of our development is given by the relationship of the new complexity classes with some complexity classes in the Turing model of computation. This relationship naturally leads to a new notion in complexity over the reals (we call it ``gap narrowness'') and to a series of completeness results in the discrete, classical setting.
Back

Smoothed analysis of complex conic condition numbers

Peter Bürgisser, Felipe Cucker, and Martin Lotz

Smoothed analysis of complexity bounds and condition numbers has been done, so far, on a case by case basis. In this paper we consider a reasonably large class of condition numbers for problems over the complex numbers and we obtain smoothed analysis estimates for elements in this class depending only on geometric invariants of the corresponding sets of ill-posed inputs. These estimates are for a version of smoothed analysis proposed in this paper which, to the best of our knowledge, appears to be new. Several applications to linear and polynomial equation solving show that estimates obtained in this way are easy to derive and quite accurate.
Back

On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety

Peter Scheiblechner

We extend the lower bounds on the complexity of computing Betti numbers proved in [Buergisser, Cucker] to complex algebraic varieties. More precisely, we first prove that the problem of deciding connectedness of a complex affine or projective variety given as the zero set of integer polynomials is PSPACE-hard. Then we prove FPSPACE-hardness for the more general problem of computing Betti numbers of fixed order of a complex projective variety.
Back

General formulas for the smoothed analysis of condition numbers

Peter Bürgisser, Felipe Cucker, and Martin Lotz

We provide estimates on the volume of tubular neighbourhoods around a subvariety \Sigma of real projective space, intersected with a disk of radius \sigma. The bounds are in terms of \sigma, the dimension of the ambient space, and the degree of equations defining \Sigma. We use these bounds to obtain smoothed analysis estimates for some conic condition numbers.
Back

Average volume, curvatures, and Euler characteristic of random real algebraic varieties

Peter Bürgisser

We determine the expected curvature polynomial of random real projective varieties given as the zero set of independent random polynomials with Gaussian distribution, whose distribution is invariant under the action of the orthogonal group. In particular, the expected Euler characteristic of such random real projective varieties is found. This considerably extends previously known results on the number of roots, the volume, and the Euler characteristic of the solution set of random polynomial equations.
Back

On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

Peter Bürgisser

Let \tau(n) denote the minimum number of arithmetic operations sufficient to build the integer n from the constant 1. We prove that if there are arithmetic circuits for computing the permanent of n by n matrices having size polynomial in n, then \tau(n!) is polynomially bounded in \log n. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials \prod_{k=1}^n (X-k) and the Taylor approximations \sum_{k=0}^n \frac1{k!} X^k and \sum_{k=1}^n \frac1{k} X^k of exp and log, respectively, can be computed by arithmetic circuits of size polynomial in \log n (allowing divisions). This connects several so far unrelated conjectures in algebraic complexity.
Back

The probability that a slightly perturbed numerical analysis problem is difficult

Peter Bürgisser, Felipe Cucker, and Martin Lotz

We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of $ \varepsilon$-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius $\sigma$. Besides $\varepsilon$ and $\sigma$, this bound depends only on the dimension of the sphere and on the degree of the defining equations.
Back

Differential Forms in Computational Algebraic Geometry

Peter Bürgisser and Peter Scheiblechner

We give a uniform method for the two problems #CC_C and #IC_C of counting connected and irreducible components of complex algebraic varieties, respectively. Our algorithms are purely algebraic, i.e., they use only the field structure of C. They work efficiently in parallel and can be implemented by algebraic circuits of polynomial depth, i.e., in parallel polynomial time. The design of our algorithms relies on the concept of algebraic differential forms. A further important building block is an algorithm of Szanto (1997) computing a variant of characteristic sets. The crucial complexity parameter for #IC_C turns out to be the number of equations. We describe a randomised algorithm solving #IC_C for a fixed number of rational equations given by straight-line programs (slps), which runs in parallel polylogarithmic time in the length and the degree of the slps.
Back

Average Euler Characteristic of Random Real Algebraic Varieties

Peter Bürgisser

We determine the expected curvature polynomial of real projective varieties given as the zero set of independent random polynomials with Gaussian distribution, which is invariant under the orthogonal group. In particular, the expected Euler characteristic of such random real projective varieties is found. This considerably extends previously known results on the number of roots, the volume, and the Euler characteristic of the real solution set of random polynomial equations.
Back

On the Complexity of Counting Components of Algebraic Varieties

Peter Bürgisser and Peter Scheiblechner

We give a uniform method for the two problems #CC_C and #IC_C of counting the connected and irreducible components of complex algebraic varieties, respectively. Our algorithms are purely algebraic, i.e., they use only the field structure of C. They work in parallel polynomial time, i.e., they can be implemented by algebraic circuits of polynomial depth. The design of our algorithms relies on the concept of algebraic differential forms. A further important building block is an algorithm of Szanto computing a variant of characteristic sets. Furthermore, we use these methods to obtain a parallel polynomial time algorithm for computing the Hilbert polynomial of a projective variety which is arithmetically Cohen-Macaulay.
Back

The complexity of computing Kronecker coefficients

Peter Bürgisser and Christian Ikenmeyer

Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem KC of computing Kronecker coefficients is very difficult. More specifically, we prove that KC is #P-hard and contained in the complexity class Gap. Formally, this means that the existence of a polynomial time algorithm for KC is equivalent to the existence of a polynomial time algorithm for evaluating permanents. Back

Coverage Processes on Spheres and Condition Numbers for Linear Programming

Peter Bürgisser, Felipe Cucker, and Martin Lotz

This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let p(n,m,\a) be the probability that n spherical caps of angular radius \a in S^m do not cover the whole sphere S^m. We give an exact formula for p(n,m,\a) in the case \a\in [\pi/2,\pi] and an upper bound for p(n,m,\a) in the case \a\in [0,\pi/2], which tends to p(n,m,\pi/2) when \a\to\pi/2. In the case \a\in [0,\pi/2] this yields upper bounds for the expected number of spherical caps of radius \a that are needed to cover S^m. Secondly, we study the condition number \CC(A) of the linear programming feasibility problem \exists x\in\R^{m+1}\, Ax\le 0,\, x\ne 0, where A\in\R^{n\times (m+1)} is randomly chosen according to the standard normal distribution. We exactly determine the distribution of \CC(A) conditioned to A being feasible and provide an upper bound on the distribution function in the infeasible case. Using these results, we show that \bE(\ln\CC(A))\le 2\ln(m+1) + 3.31 for all n>m, the sharpest bound for this expectancy as of today. Both agendas are related through a result which translates between coverage and condition. Back

Robust Smoothed Analysis of a Condition Number for Linear Programming

Peter Bürgisser and Dennis Amelunxen

We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem \exists x\in\R^{m+1} Ax < 0. Suppose that \bar{A} is any matrix with rows \bar{a_i} of euclidean norm 1 and, independently for all i, let a_i be a random perturbation of \bar{a_i} following the uniform distribution in the spherical disk in S^m of angular radius \arcsin\sigma and centered at \bar{a_i}. We prove that E(\ln C(A)) = O(mn / \sigma). A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan, Spielman, and Teng [arXiv:cs.DS/0302011]. Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius \arcsin\sigma, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser, Cucker, and Lotz (Math.\ Comp.\ 77, No. 263, 2008) with techniques of Dunagan et al. Back

Counting Irreducible Components of Complex Algebraic Varieties

Peter Bürgisser and Peter Scheiblechner

We present an algorithm for counting the irreducible components of a complex algebraic variety defined by a fixed number of polynomials encoded as straight-line programs (slps). It runs in polynomial time in the Blum-Shub-Smale (BSS) model and in randomized parallel polylogarithmic time in the Turing model, both measured in the lengths and degrees of the slps. Our algorithm is obtained from an explicit version of Bertini's theorem. For its analysis we further develop a general complexity theoretic framework appropriate for algorithms in algebraic geometry. Back

Smoothed Analysis of Condition Numbers

Peter Bürgisser

The running time of many iterative numerical algorithms is dominated by the condition number of the input, a quantity measuring the sensitivity of the solution with regard to small perturbations of the input. Examples are iterative methods of linear algebra, interior-point methods of linear and convex optimization, as well as homotopy methods for solving systems of polynomial equations. Thus a probabilistic analysis of these algorithms can be reduced to the analysis of the distribution of the condition number for a random input. This approach was elaborated for average-case complexity by many researchers. The goal of this survey is to explain how average-case analysis can be naturally refined in the sense of smoothed analysis. The latter concept, introduced by Spielman and Teng in 2001, aims at showing that for all real inputs (even ill-posed ones), and all slight random perturbations of that input, it is unlikely that the running time will be large. A recent general result of B\"urgisser, Cucker and Lotz (2008) gives smoothed analy\-sis estimates for a variety of applications. Its proof boils down to local bounds on the volume of tubes around a real algebraic hypersurface in a sphere. This is achieved by bounding the integrals of absolute curvature of smooth hypersurfaces in terms of their degree via the principal kinematic formula of integral geometry and B\'ezout's theorem. Back

A max-flow algorithm for positivity of Littlewood-Richardson coefficients

Peter Bürgisser and Christian Ikenmeyer

Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group GL(n,C). They have a wide variety of interpretations in combinatorics, representation theory and geometry. Mulmuley and Sohoni pointed out that it is possible to decide the positivity of Littlewood-Richardson coefficients in polynomial time. This follows by combining the saturation property of Littlewood-Richardson coefficients (shown by Knutson and Tao 1999) with the well-known fact that linear optimization is solvable in polynomial time. We design an explicit combinatorial polynomial time algorithm for deciding the positivity of Littlewood-Richardson coefficients. This algorithm is highly adapted to the problem and it is based on ideas from the theory of optimizing flows in networks. Back

An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP

Peter Bürgisser, Joseph M. Landsberg, Laurent Manivel, and Jerzy Weyman

We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the Geometric Complexity Theory program to prove a variant of Valiant's algebraic analog of the P not equal to NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate. Back

Oberwolfach Report No. 52/2009 on "Complexity Theory"

organised by Peter Bürgisser, Joachim von zur Gathen, Oded Goldreich, and Madhu Sudan

Computational Complexity Theory is the mathematical study of the intrinsic power and limitations of computational resources like time, space, or randomness. The current workshop focused on recent developments in various sub-areas including arithmetic complexity, Boolean complexity, communication complexity, cryptography, probabilistic proof systems, pseudorandomness, and quantum computation. Many of the developements are related to diverse mathematical elds such as algebraic geometry, combinatorial number theory, probability theory, quantum mechanics, representation theory, and the theory of error-correcting codes. Back

On a Problem Posed by Steve Smale

Peter Bürgisser and Felipe Cucker

The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of $n$ complex polynomials in $n$ unknowns in time polynomial, on the average, in the size $N$ of the input system. A partial solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who exhibited a randomized algorithm doing so. In this paper we further extend this result in several directions. Firstly, we exhibit a linear homotopy algorithm that efficiently implements a non-constructive idea of Mike Shub. This algorithm is then used in a randomized algorithm, call it LV, a la Beltran-Pardo. Secondly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and $\s^{-1}$, where $\s$ controls the size of of the random perturbation of the input systems. Thirdly, we perform a condition-based analysis of LV. That is, we give a bound, for each system $f$, of the expected running time of LV with input $f$. In addition to its dependence on $N$ this bound also depends on the condition of $f$. Fourthly, and to conclude, we return to Smale's 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is $N^{O(\log\log N)}$. This is nearly a solution to Smale's 17th problem. Back

Nonvanishing of Kronecker coefficients for rectangular shapes

Peter Bürgisser, Matthias Christandl and Christian Ikenmeyer

We prove that for any partition $(\lambda_1,...,\lambda_{d^2})$ of size $\ell d$ there exists $k\ge 1$ such that the tensor square of the irreducible representation of the symmetric group $S_{k\ell d}$ with respect to the rectangular partition $(k\ell,...,k\ell)$ contains the irreducible representation corresponding to the stretched partition $(k\lambda_1,...,k\lambda_{d^2})$. We also prove a related approximate version of this statement in which the stretching factor $k$ is effectively bounded in terms of $d$. This investigation is motivated by questions of geometric complexity theory. Back

Smoothed Analysis of Moore-Penrose Inversion

Peter Bürgisser and Felipe Cucker

We perform a smoothed analysis of the condition number of rectangular matrices. We prove that, asymptotically, the expected value of this condition number depends only of the elongation of the matrix, and not on the center and variance of the underlying probability distribution. Back

Smoothed Analysis of Condition Numbers

Peter Bürgisser

We present some recent results on the probabilistic behaviour of interior point methods for the convex conic feasibility problem and for homotopy methods solving complex polynomial equations. As suggested by Spielman and Teng, the goal is to prove that for all inputs (even ill-posed ones), and all slight random perturbations of that input, it is unlikely that the running time will be large. These results are obtained through a probabilistic analysis of the condition of the corresponding computational problems. Back

Even partitions in plethysms

Peter Bürgisser, Matthias Christandl and Christian Ikenmeyer

We prove that for all natural numbers k,n,d with k <= d and every partition lambda of size kn with at most k parts there exists an irreducible GL(d, C)-representation of highest weight 2*lambda in the plethysm Sym^k(Sym^(2n) (C^d)). This gives an affirmative answer to a conjecture by Weintraub (J. Algebra, 129 (1):103-114, 1990). Our investigation is motivated by questions of geometric complexity theory and uses ideas from quantum information theory. Back

Geometric Complexity Theory and Tensor Rank

Peter Bürgisser and Christian Ikenmeyer

Abstract: Mulmuley and Sohoni (GCT1 in SICOMP 2001, GCT2 in SICOMP 2008) proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group $G = GL(W_1)\times GL(W_2)\times GL(W_3)$ acting on the tensor product $W=W_1\otimes W_2\otimes W_3$ of complex finite dimensional vector spaces. Let $G_s = SL(W_1)\times SL(W_2)\times SL(W_3)$. A key idea from GCT2 is that the irreducible $G_s$-representations occurring in the coordinate ring of the $G$-orbit closure of a stable tensor $w\in W$ are exactly those having a nonzero invariant with respect to the stabilizer group of $w$.
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

A coordinate-free condition number for convex programming

Dennis Amelunxen and Peter Bürgisser

We introduce and analyze a natural geometric version of Renegar's condition number R for the homogeneous convex feasibility problem associated with a regular cone C subseteq R^n. Let Gr_{n,m} denote the Grassmann manifold of m-dimensional linear subspaces of R^n and consider the projection distance d_p(W_1,W_2) := ||Pi_{W_1} - Pi_{W_2}|| (spectral norm) between W_1 and W_2 in Gr_{n,m}, where Pi_{W_i} denotes the orthogonal projection onto W_i. We call C_G(W) := max { d_p(W,W')^{-1} | W' \in Sigma_m } the Grassmann condition number of W in Gr_{n,m}, where the set of ill-posed instances Sigma_m subset Gr_{n,m} is defined as the set of linear subspaces touching C. We show that if W = im(A^T) for a matrix A in R^{m\times n}, then C_G(W) \le R(A) \le C_G(W) kappa(A), where kappa(A) =||A|| ||A^\dagger|| denotes the matrix condition number. This extends work by Belloni and Freund in Math. Program. 119:95-107 (2009). Furthermore, we show that C_G(W) can as well be characterized in terms of the Riemannian distance metric on Gr_{n,m}. This differential geometric characterization of C_G(W) is the starting point of the sequel [arXiv:1112.2603] to this paper, where the first probabilistic analysis of Renegar's condition number for an arbitrary regular cone C is achieved. Back

Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

Stefan Mengel

We explore the expressivity of constraint satisfaction problems (CSPs) in the arithmetic circuit model. While CSPs are known to yield VNP-complete polynomials in the general case, we show that for different restrictions of the structure of the CSPs we get characterizations of different arithmetic circuit classes. In particular we give the first natural non-circuit characterization of VP, the class of polynomial families efficiently computable by arithmetic circuits. Back

Probabilistic analysis of the Grassmann condition number

Dennis Amelunxen and Peter Bürgisser

We perform an average analysis of the Grassmann condition number \CG(A) for the homogeneous convex feasibility problem \exists x \in C \setminus 0 : Ax=0, where C \subset R^n may be any regular cone. This in particular includes the cases of linear programming, second-order programming, and semidefinite programming. We thus give the first average analysis of convex programming, which is not restricted to linear programming. The Grassmann condition number is a geometric version of Renegar's condition number, which we have introduced recently in [arXiv:1105.4049v1]. In this work we use techniques from spherical convex geometry and differential geometry. Among other things, we will show that if the entries of A \in R^{m\times n} are chosen i.i.d. standard normal, then for any regular cone C we have E[ln \CG(A)] < 1.5 ln(n)+1.5. Back

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Hervé Fournier, Guillaume Malod and Stefan Mengel

We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems before. We also study these questions for circuits computing multilinear polynomials. Back

Deciding Positivity of Littlewood-Richardson Coefficients

Peter Bürgisser and Christian Ikenmeyer

Starting with Knutson and Tao's hive model (in J. Amer. Math. Soc., 1999) we characterize the Littlewood-Richardson coefficient $c_{\lambda,\mu}^\nu$ of given partitions $\lambda,\mu,\nu\in N^n$ as the number of capacity achieving hive flows on the honeycomb graph. Based on this, we design a polynomial time algorithm for deciding $c_{\lambda,\mu}^\nu >0$. This algorithm is easy to state and takes $O(n^3 \log \nu_1)$ arithmetic operations and comparisons. We further show that the capacity achieving hive flows can be seen as the vertices of a connected graph, which leads to new structural insights into Littlewood-Richardson coefficients. Back

Intrinsic volumes of symmetric cones

Dennis Amelunxen and Peter Bürgisser

We compute the intrinsic volumes of the cone of positive semidefinite matrices over the real numbers, over the complex numbers, and over the quaternions, in terms of integrals related to Mehta's integral. Several applications for the probabilistic analysis of semidefinite programming are given. Back

Small Littlewood-Richardson coefficients

Christian Ikenmeyer

We develop structural insights into the Littlewood-Richardson graph, whose number of vertices equals the Littlewood-Richardson coefficient cλ,μν for given partitions λ, μ, and ν. This graph was first introduced by Bürgisser and Ikenmeyer in arXiv:1204.2484, where its connectedness was proved. Our insights are useful for the design of algorithms for computing the Littlewood-Richardson coefficient: We design an algorithm for the exact computation of cλ,μν with running time O((cλ,μν)2 poly(n)), where λ, μ, and ν are partitions of length at most n. Moreover, we introduce an algorithm for deciding whether cλ,μν >= t whose running time is O(t2 poly(n)). Even the existence of a polynomial-time algorithm for deciding whether cλ,μν >= 2 is a nontrivial new result on its own. Our insights also lead to the proof of a conjecture by King, Tollu, and Toumazet posed in 2004, stating that cλ,μν = 2 implies cMλ,MμMν = M + 1 for all M. Here, the stretching of partitions is defined componentwise. Back

Explicit Lower Bounds via Geometric Complexity Theory

Peter Bürgisser and Christian Ikenmeyer

We prove the lower bound R(Mm) >= 3/2 m2 - 2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's geometric complexity theory (GCT) program. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is the new combinatorial concept of obstruction designs, which encode highest weight vectors in Symd\otimes3(Cn)* and provide new insights into Kronecker coefficients. Back

Structural Tractability of Counting of Solutions to Conjunctive Queries

Arnaud Durand and Stefan Mengel

In this paper we explore the problem of counting solutions to conjunctive queries. We consider a parameter called the quantified star size of a formula φ which measures how the free variables are spread in φ. We show that for conjunctive queries that admit nice decomposition properties (such as being of bounded treewidth or generalized hypertree width) bounded quantified star size exactly characterizes the classes of queries for which counting the number of solutions is tractable. This also allows us to fully characterize the conjunctive queries for which counting the solutions is tractable in the case of bounded arity.
To illustrate the applicability of our results, we also show that computing the quantified star size of a formula is possible in time nO(k) for queries of generalized hypertree width k. Furthermore, quantified star size is even fixed parameter tractable parameterized by some other width measures, while it is W[1]-hard for generalized hypertree width and thus unlikely to be fixed parameter tractable. We finally show how to compute an approximation of quantified star size in polynomial time where the approximation ratio depends on the width of the input. Back

Author: P. Buergisser. Last change: November 2, 2012 by C. Ikenmeyer