Joos Heintz

  1. On the intrinsic complexity of elimination problems in effective Algebraic Geometry.

    Authors: Joos Heintz, Bart Kuijpers, Andres Rojas Paredes
    Subjects: Computational Complexity
    Abstract

    The representation of polynomials by arithmetic circuits evaluating them is
    an alternative data structure which allowed considerable progress in polynomial
    equation solving in the last fifteen years. We present a circuit based
    computation model which captures all known symbolic elimination algorithms in
    effective algebraic geometry and show the intrinsically exponential complexity
    character of elimination in this complexity model.

Syndicate content