Book Chapters

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

in Complexity of computations and proofs 13 pp. 73-152

• Authors: Bürgisser, P. and Cucker, F.
• Editors: Jan Krajicek
• Published: . Quaderni di Matematica, 2005.

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.

Incorporating Severity Variations into Credit Risk [2]

in Innovations in Risk Management pp. 533-567

• Authors: Bürgisser, P., Kurth, A. and Wagner, A.
• Editors: P. Jorion
• Published: . Incisive Media Investments Limited, 2004.

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.

Lower Bounds and Real Algebraic Geometry [3]

in Algorithmic and Quantitative Real Algebraic Geometry 60 pp. 35-54

• Authors: Bürgisser, P.
• Editors: Saugata Basu and Laureano Gonzalez-Vega
• Published: . AMS, 2003.

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.

Algebraic Complexity Theory [4]

in Handbook of Computer Algebra pp. 125-128

• Authors: Bürgisser, P., Clausen, M. H. and Shokrollahi, M. A.
• Editors: J. Grabmeier and E. Kaltofen and V. Weispfenning
• Published: . Springer Verlag, 2003.