64 citations · 414 across the 34 of their papers we have counts for
14 papers · 1 filter
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 Complexity of Factors of Multivariate Polynomials
Peter Bürgisser
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 i…
The real tau-conjecture is true on average
Irénée Briquel, Peter Bürgisser
Koiran's real -conjecture claims that the number of real zeros of a structured polynomial given as a sum of products of real sparse polynomials, each with at most mo…