Search Results

Documents authored by Bürgisser, Peter


Document
Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture

Authors: Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)


Abstract
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 questions and structures in physics, mathematics, computer science, optimization, and more. Accordingly, it is of high interest to understand their computational complexity. Recently, Bürgisser et al. (2021) gave the first polynomial-time algorithms for orbit problems of torus actions, that is, actions of commutative continuous groups on Euclidean space. In this work, motivated by theoretical and practical applications, we study the computational complexity of robust generalizations of these orbit problems, which amount to approximating the distance of orbits in ℂⁿ up to a factor γ ≥ 1. In particular, this allows deciding whether two inputs are approximately in the same orbit or far from being so. On the one hand, we prove the NP-hardness of this problem for γ = n^Ω(1/log log n) by reducing the closest vector problem for lattices to it. On the other hand, we describe algorithms for solving this problem for an approximation factor γ = exp(poly(n)). Our algorithms combine tools from invariant theory and algorithmic lattice theory, and they also provide group elements witnessing the proximity of the given orbits (in contrast to the algebraic algorithms of prior work). We prove that they run in polynomial time if and only if a version of the famous number-theoretic abc-conjecture holds - establishing a new and surprising connection between computational complexity and number theory.

Cite as

Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 14:1-14:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:LIPIcs.CCC.2024.14,
  author =	{B\"{u}rgisser, Peter and Do\u{g}an, Mahmut Levent and Makam, Visu and Walter, Michael and Wigderson, Avi},
  title =	{{Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{14:1--14:48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.14},
  URN =		{urn:nbn:de:0030-drops-204100},
  doi =		{10.4230/LIPIcs.CCC.2024.14},
  annote =	{Keywords: computational invariant theory, geometric complexity theory, orbit problems, abc-conjecture, closest vector problem}
}
Document
Polynomial Time Algorithms in Invariant Theory for Torus Actions

Authors: Peter Bürgisser, M. Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, namely, orbit equality, orbit closure intersection, and orbit closure containment. These capture and relate to a variety of problems within mathematics, physics and computer science, optimization and statistics. These orbit problems extend the more basic null cone problem, whose algorithmic complexity has seen significant progress in recent years. In this paper, we initiate a study of these problems by focusing on the actions of commutative groups (namely, tori). We explain how this setting is motivated from questions in algebraic complexity, and is still rich enough to capture interesting combinatorial algorithmic problems. While the structural theory of commutative actions is well understood, no general efficient algorithms were known for the aforementioned problems. Our main results are polynomial time algorithms for all three problems. We also show how to efficiently find separating invariants for orbits, and how to compute systems of generating rational invariants for these actions (in contrast, for polynomial invariants the latter is known to be hard). Our techniques are based on a combination of fundamental results in invariant theory, linear programming, and algorithmic lattice theory.

Cite as

Peter Bürgisser, M. Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Polynomial Time Algorithms in Invariant Theory for Torus Actions. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 32:1-32:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:LIPIcs.CCC.2021.32,
  author =	{B\"{u}rgisser, Peter and Do\u{g}an, M. Levent and Makam, Visu and Walter, Michael and Wigderson, Avi},
  title =	{{Polynomial Time Algorithms in Invariant Theory for Torus Actions}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{32:1--32:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.32},
  URN =		{urn:nbn:de:0030-drops-143062},
  doi =		{10.4230/LIPIcs.CCC.2021.32},
  annote =	{Keywords: computational invariant theory, geometric complexity theory, orbit closure intersection problem}
}
Document
Invited Talk
Optimization, Complexity and Invariant Theory (Invited Talk)

Authors: Peter Bürgisser

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
Invariant and representation theory studies symmetries by means of group actions and is a well established source of unifying principles in mathematics and physics. Recent research suggests its relevance for complexity and optimization through quantitative and algorithmic questions. The goal of the talk is to give an introduction to new algorithmic and analysis techniques that extend convex optimization from the classical Euclidean setting to a general geodesic setting. We also point out surprising connections to a diverse set of problems in different areas of mathematics, statistics, computer science, and physics.

Cite as

Peter Bürgisser. Optimization, Complexity and Invariant Theory (Invited Talk). In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{burgisser:LIPIcs.STACS.2021.1,
  author =	{B\"{u}rgisser, Peter},
  title =	{{Optimization, Complexity and Invariant Theory}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.1},
  URN =		{urn:nbn:de:0030-drops-136460},
  doi =		{10.4230/LIPIcs.STACS.2021.1},
  annote =	{Keywords: geometric invariant theory, geodesic optimization, non-commutative optimization, null cone, operator scaling, moment polytope, orbit closure intersection, geometric programming}
}
Document
Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory

Authors: Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)


Abstract
Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).

Cite as

Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:LIPIcs.ITCS.2018.24,
  author =	{B\"{u}rgisser, Peter and Garg, Ankit and Oliveira, Rafael and Walter, Michael and Wigderson, Avi},
  title =	{{Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.24},
  URN =		{urn:nbn:de:0030-drops-83510},
  doi =		{10.4230/LIPIcs.ITCS.2018.24},
  annote =	{Keywords: alternating minimization, tensors, scaling, quantum marginal problem, null cone, invariant theory, geometric complexity theory}
}
Document
Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242)

Authors: Peter Bürgisser, Felipe Cucker, Marek Karpinski, and Nicolai Vorobjov

Published in: Dagstuhl Reports, Volume 5, Issue 6 (2016)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15242 "Complexity of Symbolic and Numerical Problems".

Cite as

Peter Bürgisser, Felipe Cucker, Marek Karpinski, and Nicolai Vorobjov. Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242). In Dagstuhl Reports, Volume 5, Issue 6, pp. 28-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{burgisser_et_al:DagRep.5.6.28,
  author =	{B\"{u}rgisser, Peter and Cucker, Felipe and Karpinski, Marek and Vorobjov, Nicolai},
  title =	{{Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242)}},
  pages =	{28--47},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{6},
  editor =	{B\"{u}rgisser, Peter and Cucker, Felipe and Karpinski, Marek and Vorobjov, Nicolai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.6.28},
  URN =		{urn:nbn:de:0030-drops-55066},
  doi =		{10.4230/DagRep.5.6.28},
  annote =	{Keywords: Symbolic computation, Algorithms in real algebraic geometry, Complexity lower bounds, Geometry of numerical algorithms}
}
Document
Computational Counting (Dagstuhl Seminar 13031)

Authors: Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran

Published in: Dagstuhl Reports, Volume 3, Issue 1 (2013)


Abstract
Dagstuhl Seminar 13031 "Computational Counting" was held from 13th to 18th January 2013, at Schloss Dagstuhl -- Leibnitz Center for Informatics. A total of 43 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting.

Cite as

Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran. Computational Counting (Dagstuhl Seminar 13031). In Dagstuhl Reports, Volume 3, Issue 1, pp. 47-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{burgisser_et_al:DagRep.3.1.47,
  author =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark and Koiran, Pascal},
  title =	{{Computational Counting (Dagstuhl Seminar 13031)}},
  pages =	{47--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{1},
  editor =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark and Koiran, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.1.47},
  URN =		{urn:nbn:de:0030-drops-40087},
  doi =		{10.4230/DagRep.3.1.47},
  annote =	{Keywords: Computational complexity, counting problems, graph polynomials, holographic algorithms, statistical physics, constraint satisfaction}
}
Document
10481 Abstracts Collection – Computational Counting

Authors: Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum

Published in: Dagstuhl Seminar Proceedings, Volume 10481, Computational Counting (2011)


Abstract
From November 28 to December 3 2010, the Dagstuhl Seminar 10481 ``Computational Counting'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum. 10481 Abstracts Collection – Computational Counting. In Computational Counting. Dagstuhl Seminar Proceedings, Volume 10481, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:DagSemProc.10481.1,
  author =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{10481 Abstracts Collection – Computational Counting}},
  booktitle =	{Computational Counting},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10481},
  editor =	{Peter B\"{u}rgisser and Leslie Ann Goldberg and Mark Jerrum},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10481.1},
  URN =		{urn:nbn:de:0030-drops-29453},
  doi =		{10.4230/DagSemProc.10481.1},
  annote =	{Keywords: Computational complexity, counting problems, holographic algorithms, statistical physics, constraint satisfaction}
}
Document
10481 Executive Summary – Computational Counting

Authors: Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum

Published in: Dagstuhl Seminar Proceedings, Volume 10481, Computational Counting (2011)


Abstract
From November 28 to December 3 2010, the Dagstuhl seminar 10481 ``Computational Counting'' was held in Schloss Dagstuhl – Leibnitz Center for Informatics. 36 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting.

Cite as

Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum. 10481 Executive Summary – Computational Counting. In Computational Counting. Dagstuhl Seminar Proceedings, Volume 10481, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:DagSemProc.10481.2,
  author =	{B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{10481 Executive Summary – Computational Counting}},
  booktitle =	{Computational Counting},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10481},
  editor =	{Peter B\"{u}rgisser and Leslie Ann Goldberg and Mark Jerrum},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10481.2},
  URN =		{urn:nbn:de:0030-drops-29441},
  doi =		{10.4230/DagSemProc.10481.2},
  annote =	{Keywords: Computational complexity, counting problems, holographic algorithms, statistical physics, constraint satisfaction}
}
Document
On the Complexity of Numerical Analysis

Authors: Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)


Abstract
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the following problem, which we call PosSlp: Given a division-free straight-line program producing an integer N, decide whether N>0. We show that OrdSlp lies in the counting hierarchy, and combining our results with work of Tiwari, we show that the Euclidean Traveling Salesman Problem lies in the counting hierarchy – the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.

Cite as

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the Complexity of Numerical Analysis. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{allender_et_al:DagSemProc.06111.12,
  author =	{Allender, Eric and B\"{u}rgisser, Peter and Kjeldgaard-Pedersen, Johan and Miltersen, Peter Bro},
  title =	{{On the Complexity of Numerical Analysis}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.12},
  URN =		{urn:nbn:de:0030-drops-6130},
  doi =		{10.4230/DagSemProc.06111.12},
  annote =	{Keywords: Blum-Shub-Smale Model, Euclidean Traveling Salesman Problem, Counting Hierarchy}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail