PBPeter Bürgisser

Peter Bürgisser

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Nonarchimedean integral geometry

    by Peter Bürgisser, Avinash Kulkarni, Antonio Lerario

    Let K be a nonarchimedean local field of characteristic zero with valuation ring R , for instance, $$K=\mathbb {Q}_p$$ K = Q p and $$R=\mathbb {Z}_p$$ R = 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$$ 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

    by Paul Breiding, Peter Bürgisser, Antonio Lerario, Léo Mathis

    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

    by Peter Bürgisser, Avinash Kulkarni, Antonio Lerario

    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

    On the Hardness of PosSLP

    by Peter Bürgisser, Gorav Jindal

    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

    Rigid continuation paths II. structured polynomial systems

    by Peter Bürgisser, Felipe Cucker, Pierre Lairez

    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

    by Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, Avi Wigderson

    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

    by 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 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.