Peter Bürgisser
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Peter Bürgisser has a total of 36 co-authors. Here are the top co-authors by number of shared publications:
- Felipe Cucker
City Univ Hong Kong, Dept Math, Hong Kong, Peoples R China
10 shared publications - Antonio Lerario
SISSA, Trieste, Italy
5 shared publications - Carlos Beltrán
Universidad de Cantabria
3 shared publications - Diego Armentano
Universidad de la República
3 shared publications - Michael Shub
Universidad de Buenos Aires
3 shared publications - Pierre Lairez
Inria Université Paris-Saclay Palaiseau France
3 shared publications
Latest Publications
- Open Access
- 5 January 2026
- Published by Springer Nature in Selecta Mathematica
- Vol. 32 (1) , 10
Nonarchimedean integral geometry
Let K be a nonarchimedean local field of characteristic zero with valuation ring R , for instance, $$K=\mathbb {Q}_p$$ and $$R=\mathbb {Z}_p$$ . We prove a general integral geometric formula for K –analytic groups and homogeneous K –analytic spaces, analogous to the corresponding result over the reals. This generalizes the p –adic integral geometric formula for projective spaces recently discovered by Kulkarni and Lerario, e.g., to the setting of Grassmannians. Based on this, we outline the construction of a nonarchimedean probabilistic Schubert Calculus. For this purpose, we characterize the relative position of two subspaces of $$K^n$$ by a position vector, a nonarchimedean analogue of the notion of principal angles, and we study the probability distribution of the position vector for random uniform subspaces. We then use this to compute the volume of special Schubert varieties over K . As a second application of the general integral geometry formula, we initiate the study of random fewnomial systems over nonarchimedean fields, bounding, and in some cases exactly determining, the expected number of zeros of such random systems.- 5 January 2026
- Published by Springer Nature in Selecta Mathematica
- Vol. 32 (1) , 10
Open AccessNonarchimedean integral geometry
Let K be a nonarchimedean local field of characteristic zero with valuation ring R , for instance, $$K=\mathbb {Q}_p$$ and $$R=\mathbb {Z}_p$$ . We prove a general integral geometric formula for K –analytic groups and homogeneous K –analytic spaces, analogous to the corresponding result over the reals. This generalizes the p –adic integral geometric formula for projective spaces recently discovered by Kulkarni and Lerario, e.g., to the setting of Grassmannians. Based on this, we outline the construction of a nonarchimedean probabilistic Schubert Calculus. For this purpose, we characterize the relative position of two subspaces of $$K^n$$ by a position vector, a nonarchimedean analogue of the notion of principal angles, and we study the probability distribution of the position vector for random uniform subspaces. We then use this to compute the volume of special Schubert varieties over K . As a second application of the general integral geometry formula, we initiate the study of random fewnomial systems over nonarchimedean fields, bounding, and in some cases exactly determining, the expected number of zeros of such random systems. - Open Access
Probabilistic intersection theory in Riemannian homogeneous spaces
Let $M=G/H$ be a Riemannian homogeneous space, where $G$ is a compact Lie group with closed subgroup $H$. Classical intersection theory states that the de Rham cohomology ring of $M$ describes the signed count of intersection points of submanifolds $Y_1, \ldots, Y_s$ of $M$ in general position, when the codimensions add up to $\dim M$. We introduce the probabilistic intersection ring $\mathrm{H}_{\mathbb E}(M)$, whose multiplication describes the unsigned count of intersection points, when the $Y_i$ are randomly moved by independent uniformly random elements of $G$. The probabilistic intersection ring $\mathrm{H}_{\mathbb E}(M)$ has the structure of a graded commutative and associative real Banach algebra. It is defined as a quotient of the ring of Grassmann zonoids of a fixed cotangent space $V$ of $M$. The latter was introduced by the authors in [Adv. Math. 402, 2022]. There is a close connection to valuations of convex bodies: $\mathrm{H}_{\mathbb E}(M)$ can be interpreted as a subspace of the space of translation invariant, even, continuous valuations on $V$, whose multiplication coincides with Alesker's multiplication for smooth valuations. We describe the ring structure of the probabilistic intersection ring for spheres, real projective space and complex projective space, relying on Fu [J. Diff. Geo. 72(3), 2006] for the latter case. From this, we derive an interesting probabilistic intersection formula in complex projective space. Finally, we initiate the investigation of the probabilistic intersection ring for real Grassmannians, outlining the construction of a probabilistic version of Schubert Calculus.Open AccessProbabilistic intersection theory in Riemannian homogeneous spaces
Let $M=G/H$ be a Riemannian homogeneous space, where $G$ is a compact Lie group with closed subgroup $H$. Classical intersection theory states that the de Rham cohomology ring of $M$ describes the signed count of intersection points of submanifolds $Y_1, \ldots, Y_s$ of $M$ in general position, when the codimensions add up to $\dim M$. We introduce the probabilistic intersection ring $\mathrm{H}_{\mathbb E}(M)$, whose multiplication describes the unsigned count of intersection points, when the $Y_i$ are randomly moved by independent uniformly random elements of $G$. The probabilistic intersection ring $\mathrm{H}_{\mathbb E}(M)$ has the structure of a graded commutative and associative real Banach algebra. It is defined as a quotient of the ring of Grassmann zonoids of a fixed cotangent space $V$ of $M$. The latter was introduced by the authors in [Adv. Math. 402, 2022]. There is a close connection to valuations of convex bodies: $\mathrm{H}_{\mathbb E}(M)$ can be interpreted as a subspace of the space of translation invariant, even, continuous valuations on $V$, whose multiplication coincides with Alesker's multiplication for smooth valuations. We describe the ring structure of the probabilistic intersection ring for spheres, real projective space and complex projective space, relying on Fu [J. Diff. Geo. 72(3), 2006] for the latter case. From this, we derive an interesting probabilistic intersection formula in complex projective space. Finally, we initiate the investigation of the probabilistic intersection ring for real Grassmannians, outlining the construction of a probabilistic version of Schubert Calculus. - Open Access
Nonarchimedean integral geometry
Let $K$ be a nonarchimedean local field of characteristic zero with valuation ring $R$, for instance, $K=\mathbb{Q}_p$ and $R=\mathbb{Z}_p$. We prove a general integral geometric formula for $K$-analytic groups and homogeneous $K$-analytic spaces, analogous to the corresponding result over the reals. This generalizes the $p$-adic integral geometric formula for projective spaces recently discovered by Kulkarni and Lerario, e.g., to the setting of Grassmannians. Based on this, we outline the construction of a nonarchimedean probabilistic Schubert Calculus. For this purpose, we characterize the relative position of two subspaces of $K^n$ by a position vector, a nonarchimedean analogue of the notion of principal angles, and we study the probability distribution of the position vector for random uniform subspaces. We then use this to compute the volume of special Schubert varieties over $K$. As a second application of the general integral geometry formula, we initiate the study of random fewnomial systems over nonarchimedean fields, bounding, and in some cases exactly determining, the expected number of zeros of such random systems.Open AccessNonarchimedean integral geometry
Let $K$ be a nonarchimedean local field of characteristic zero with valuation ring $R$, for instance, $K=\mathbb{Q}_p$ and $R=\mathbb{Z}_p$. We prove a general integral geometric formula for $K$-analytic groups and homogeneous $K$-analytic spaces, analogous to the corresponding result over the reals. This generalizes the $p$-adic integral geometric formula for projective spaces recently discovered by Kulkarni and Lerario, e.g., to the setting of Grassmannians. Based on this, we outline the construction of a nonarchimedean probabilistic Schubert Calculus. For this purpose, we characterize the relative position of two subspaces of $K^n$ by a position vector, a nonarchimedean analogue of the notion of principal angles, and we study the probability distribution of the position vector for random uniform subspaces. We then use this to compute the volume of special Schubert varieties over $K$. As a second application of the general integral geometry formula, we initiate the study of random fewnomial systems over nonarchimedean fields, bounding, and in some cases exactly determining, the expected number of zeros of such random systems. - Open Access
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 107-115
Real zeros of mixed random fewnomial systems
- 24 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 107-115
Open AccessReal zeros of mixed random fewnomial systems
- Open Access
On the Hardness of PosSLP
The problem $\textrm{PosSLP}$ involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention within the field of computational complexity as it provides a complete characterization of the complexity associated with numerical computation. However, non-trivial lower bounds for $\textrm{PosSLP}$ remain unknown. In this paper, we demonstrate that $\textrm{PosSLP} \in \textrm{BPP}$ would imply that $\textrm{NP} \subseteq \textrm{BPP}$, under the assumption of a conjecture concerning the complexity of the radical of a polynomial proposed by Dutta, Saxena, and Sinhababu (STOC'2018). Our proof builds upon the established $\textrm{NP}$-hardness of determining if a univariate polynomial computed by an SLP has a real root, as demonstrated by Perrucci and Sabia (JDA'2005). Therefore, our lower bound for $\textrm{PosSLP}$ represents a significant advancement in understanding the complexity of this problem. It constitutes the first non-trivial lower bound for $\textrm{PosSLP}$ , albeit conditionally. Additionally, we show that counting the real roots of an integer univariate polynomial, given as input by a straight-line program, is $\#\textrm{P}$-hard.Open AccessOn the Hardness of PosSLP
The problem $\textrm{PosSLP}$ involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention within the field of computational complexity as it provides a complete characterization of the complexity associated with numerical computation. However, non-trivial lower bounds for $\textrm{PosSLP}$ remain unknown. In this paper, we demonstrate that $\textrm{PosSLP} \in \textrm{BPP}$ would imply that $\textrm{NP} \subseteq \textrm{BPP}$, under the assumption of a conjecture concerning the complexity of the radical of a polynomial proposed by Dutta, Saxena, and Sinhababu (STOC'2018). Our proof builds upon the established $\textrm{NP}$-hardness of determining if a univariate polynomial computed by an SLP has a real root, as demonstrated by Perrucci and Sabia (JDA'2005). Therefore, our lower bound for $\textrm{PosSLP}$ represents a significant advancement in understanding the complexity of this problem. It constitutes the first non-trivial lower bound for $\textrm{PosSLP}$ , albeit conditionally. Additionally, we show that counting the real roots of an integer univariate polynomial, given as input by a straight-line program, is $\#\textrm{P}$-hard. - Open Access
- 14 April 2023
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Pi
- Vol. 11
Rigid continuation paths II. structured polynomial systems
This work studies the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most ${D}$ in n variables with only $\operatorname {poly}(n, {D}) L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem.- 14 April 2023
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Pi
- Vol. 11
Open AccessRigid continuation paths II. structured polynomial systems
This work studies the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most ${D}$ in n variables with only $\operatorname {poly}(n, {D}) L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem. - Open Access
Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
This paper initiates a systematic development of a theory of non-commutative optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesically convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. These algorithms minimize the moment map (a non-commutative notion of the usual gradient) and test membership in null cones and moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which arise from this a priori non-convex, non-linear setting). This setting captures a diverse set of problems in different areas of computer science, mathematics, and physics. Several of them were solved efficiently for the first time using non-commutative methods; the corresponding algorithms also lead to solutions of purely structural problems and to many new connections between disparate fields. In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first order and a second order method, which respectively receive first and second order information on the "derivatives" of the function to be optimized. These in particular subsume all past results. The main technical work goes into identifying the key parameters of the underlying group actions which control convergence to the optimum in each of these methods. These non-commutative analogues of "smoothness" are far more complex and require significant algebraic and analytic machinery. Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We show how to bound these parameters and hence obtain efficient algorithms for null cone membership in several concrete situations. Our work points to intriguing open problems and suggests further research directions.
Open AccessTowards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
This paper initiates a systematic development of a theory of non-commutative optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesically convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. These algorithms minimize the moment map (a non-commutative notion of the usual gradient) and test membership in null cones and moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which arise from this a priori non-convex, non-linear setting). This setting captures a diverse set of problems in different areas of computer science, mathematics, and physics. Several of them were solved efficiently for the first time using non-commutative methods; the corresponding algorithms also lead to solutions of purely structural problems and to many new connections between disparate fields. In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first order and a second order method, which respectively receive first and second order information on the "derivatives" of the function to be optimized. These in particular subsume all past results. The main technical work goes into identifying the key parameters of the underlying group actions which control convergence to the optimum in each of these methods. These non-commutative analogues of "smoothness" are far more complex and require significant algebraic and analytic machinery. Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We show how to bound these parameters and hence obtain efficient algorithms for null cone membership in several concrete situations. Our work points to intriguing open problems and suggests further research directions.
- Open Access
Rigid continuation paths II. Structured polynomial systems
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 used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most {\delta} in n variables with only poly(n, {\delta}) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem.
Open AccessRigid continuation paths II. Structured polynomial systems
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 used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most {\delta} in n variables with only poly(n, {\delta}) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem.
- 4 January 2021
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 21 (5) , 1279-1316
Computing the Homology of Semialgebraic Sets. II: General Formulas
- 4 January 2021
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 21 (5) , 1279-1316
Computing the Homology of Semialgebraic Sets. II: General Formulas
- Open Access
- 6 October 2020
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 20 (6) , 1667-1668
Correction To: The Complexity of Factors of Multivariate Polynomials
- 6 October 2020
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 20 (6) , 1667-1668
Open AccessCorrection To: The Complexity of Factors of Multivariate Polynomials