64 citations · 414 across the 34 of their papers we have counts for
37 papers
Intractability of Hilbert's Nullstellensatz implies algebraic hardness of permanent
Peter Bürgisser
We study the logical relation of the P-NP separation conjecture in the Blum-Shub-Smale-model over the complex numbers with the P-NP separation conjecture in Valiant's algebraic mod…
Completeness classes in algebraic complexity theory
Peter Bürgisser
The purpose of this overview is to explain the enormous impact of Les Valiant's eponymous short conference contribution from 1979 on the development of algebraic complexity.
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Peter Bürgisser, Mahmut Levent Doğan, Visu Makam +2
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous que…
On the Hardness of PosSLP
Peter Bürgisser, Gorav Jindal
The problem involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention withi…
The zonoid algebra, generalized mixed volumes, and random determinants
Paul Breiding, Peter Bürgisser, Antonio Lerario +1
We show that every multilinear map between Euclidean spaces induces a unique, continuous, Minkowski multilinear map of the corresponding real cones of zonoids. Applied to the wedge…
Rigid continuation paths II. Structured polynomial systems
Peter Bürgisser, Felipe Cucker, Pierre Lairez
This work studies the average complexity of solving structured polynomial systems that are characterized by a low evaluation cost, as opposed to the dense random model previously u…