64 citations · 414 across the 34 of their papers we have counts for
4 papers · 1 filter
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…
Computing the Homology of Semialgebraic Sets I: Lax Formulas
Peter Bürgisser, Felipe Cucker, Josué Tonelli-Cueto
We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations ov…
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…
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
Peter Bürgisser, Cole Franks, Ankit Garg +3
We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence o…