Arrow Research search

Author name cluster

Peter Bürgisser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

FOCS Conference 2019 Conference Paper

Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes

  • Peter Bürgisser
  • Cole Franks
  • Ankit Garg 0001
  • Rafael Oliveira 0002
  • Michael Walter 0005
  • Avi Wigderson

This paper initiates a systematic development of a theory of non-commutative optimization, a setting which greatly extends ordinary (Euclidean) convex optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesic convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. More specifically, these are algorithms to minimize the moment map (a non-commutative notion of the usual gradient), and to test membership in moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which quite magically arise from this a-priori non-convex, non-linear setting). The importance of understanding this very general setting of geodesic optimization, as these works unveiled and powerfully demonstrate, is that it captures a diverse set of problems, many non-convex, in different areas of CS, math, 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, again unifying and extending much of the previous 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" in the commutative case are far more complex, and require significant algebraic and analytic machinery (much existing and some newly developed here). Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We also bound these parameters in several general cases. Our work points to intriguing open problems and suggests further research directions. We believe that extending this theory, namely understanding geodesic optimization better, is both mathematically and computationally fascinating; it provides a great meeting place for ideas and techniques from several very different research areas, and promises better algorithms for existing and yet unforeseen applications.

Details

FOCS Conference 2018 Conference Paper

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes

  • Peter Bürgisser
  • Cole Franks
  • Ankit Garg 0001
  • Rafael Oliveira 0002
  • Michael Walter 0005
  • Avi Wigderson

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 of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

Details

FOCS Conference 2016 Conference Paper

No Occurrence Obstructions in Geometric Complexity Theory

  • Peter Bürgisser
  • Christian Ikenmeyer
  • Greta Panova

The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes VP ws and VNP. Mulmuley and Sohoni [SIAM J Comput 2001] suggested 8to study a strengthened version of this conjecture over the complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of GLn2(C), which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible. However, we do not rule out the approach to the permanent versus determinant problem via multiplicity obstructions as proposed by in [32].

Details

STOC Conference 2013 Conference Paper

Explicit lower bounds via geometric complexity theory

  • Peter Bürgisser
  • Christian Ikenmeyer

We prove the lower bound R M m ) ≥ 3/2 m 2 -2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's geometric complexity theory (GCT) program. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is an explicit description of the highest weight vectors in Sym d ⊗ 3 (C n )* in terms of combinatorial objects, called obstruction designs. This description results from analyzing the process of polarization and Schur-Weyl duality.

Details

STOC Conference 2011 Conference Paper

Geometric complexity theory and tensor rank

  • Peter Bürgisser
  • Christian Ikenmeyer

Mulmuley and Sohoni [GCT1, SICOMP 2001; GCT2, SICOMP 2008] proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group G =GL(W 1 ) x GL(W 2 ) x GL(W 3 ) acting on the tensor product W=W 1 ⊗ W 2 ⊗ W 3 of complex finite dimensional vector spaces. Let G s =SL(W 1 ) x SL(W 2 ) x SL(W 3 ). A key idea from [GCT2] is that the irreducible G s -representations occurring in the coordinate ring of the G-orbit closure of a stable tensor w ∈ W are exactly those having a nonzero invariant with respect to the stabilizer group of w. However, we prove that by considering G s -representations, only trivial lower bounds on border rank can be shown. It is thus necessary to study G-representations, which leads to geometric extension problems that are beyond the scope of the subgroup restriction problems emphasized in [GCT1, GCT2] and its follow up papers. We prove a very modest lower bound on the border rank of matrix multiplication tensors using G-representations. This shows at least that the barrier for G s -representations can be overcome. To advance, we suggest the coarser approach to replace the semigroup of representations of a tensor by its moment polytope. We prove first results towards determining the moment polytopes of matrix multiplication and unit tensors.

Details

FOCS Conference 2002 Conference Paper

Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps

  • Peter Bürgisser
  • Martin Lotz

We prove lower bounds of order n log n for both the problem to multiply polynomials of degree n, and to divide polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [Proc. 34th STOC 2002] proposed for matrix multiplication. It reduces the linear problem to multiply a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [J. ACM 20, pp. 305-306, 1973] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix.

Details

MFCS Conference 2001 Invited Paper

On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity

  • Peter Bürgisser

Abstract Several models of NP-completeness in an algebraic framework of computation have been proposed in the past, each of them hinging on a fundamental hypothesis of type P≠NP. We first survey some known implications between such hypotheses and then describe attempts to establish further connections. This leads us to the problem of relating the complexity of computational and decisional tasks and naturally raises the question about the connection of the complexity of a polynomial with those of its factors. After reviewing what is known with this respect, we discuss a new result involving a concept of approximative complexity.

Details

FOCS Conference 2001 Conference Paper

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 in the framework of algebraic complexity, there are no such families of polynomial functions of p-bounded degree overfields of characteristic zero. The proof relies on a polynomial upper bound on the approximative complexity of a factor g of a polynomial f in terms of the (approximative) complexity of f and the degree of the factor g. This extends a result by E. Kaltofen (1986). The concept of approximative complexity allows us to cope with the case that a factor has an exponential multiplicity, by using a perturbation argument. Our result extends to randomized (two-sided error) decision complexity.

Details