15 Search Results for "Bürgisser, Peter"

Document
DOI: 10.4230/LIPIcs.CCC.2024.14
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
DOI: 10.4230/LIPIcs.CCC.2024.20
Lower Bounds for Set-Multilinear Branching Programs

Authors: Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka

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

Abstract
In this paper, we prove super-polynomial lower bounds for the model of sum of ordered set-multilinear algebraic branching programs, each with a possibly different ordering (∑smABP). Specifically, we give an explicit nd-variate polynomial of degree d such that any ∑smABP computing it must have size n^ω(1) for d as low as ω(log n). Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for d = poly(n), we demonstrate an exponential lower bound. This result generalizes the seminal work of Nisan (STOC, 1991), which proved an exponential lower bound for a single ordered set-multilinear ABP. The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (TAMC, 2024), which showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs - for a polynomial of sufficiently low degree - would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant’s longstanding conjecture that the permanent polynomial can not be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by O(log n/ log log n), then it would imply super-polynomial lower bounds against general ABPs. Our results strengthen the works of Arvind & Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi & Saxena (TAMC, 2024), as well as the works of Ramya & Rao (Theor. Comput. Sci., 2020) and Ghoshal & Rao (International Computer Science Symposium in Russia, 2021), each of which established lower bounds for related or restricted versions of this model. They also strongly answer a question from the former two, which asked to prove super-polynomial lower bounds for general ∑smABP.
Cite as

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. Lower Bounds for Set-Multilinear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2024.20,
  author =	{Chatterjee, Prerona and Kush, Deepanshu and Saraf, Shubhangi and Shpilka, Amir},
  title =	{{Lower Bounds for Set-Multilinear Branching Programs}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{20:1--20:20},
  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.20},
  URN =		{urn:nbn:de:0030-drops-204167},
  doi =		{10.4230/LIPIcs.CCC.2024.20},
  annote =	{Keywords: Lower Bounds, Algebraic Branching Programs, Set-multilinear polynomials}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.12
From Proof Complexity to Circuit Complexity via Interactive Protocols

Authors: Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Folklore in complexity theory suspects that circuit lower bounds against NC¹ or P/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishing such a connection formally, however, is already daunting, as it would imply the breakthrough separation NEXP ⊈ P/poly, as recently observed by Pich and Santhanam [Pich and Santhanam, 2023]. We show such a connection conditionally for the Implicit Extended Frege proof system (iEF) introduced by Krajíček [Krajíček, 2004], capable of formalizing most of contemporary complexity theory. In particular, we show that if iEF proves efficiently the standard derandomization assumption that a concrete Boolean function is hard on average for subexponential-size circuits, then any superpolynomial lower bound on the length of iEF proofs implies #P ⊈ FP/poly (which would in turn imply, for example, PSPACE ⊈ P/poly). Our proof exploits the formalization inside iEF of the soundness of the sum-check protocol of Lund, Fortnow, Karloff, and Nisan [Lund et al., 1992]. This has consequences for the self-provability of circuit upper bounds in iEF. Interestingly, further improving our result seems to require progress in constructing interactive proof systems with more efficient provers.
Cite as

Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arteche_et_al:LIPIcs.ICALP.2024.12,
  author =	{Arteche, Noel and Khaniki, Erfan and Pich, J\'{a}n and Santhanam, Rahul},
  title =	{{From Proof Complexity to Circuit Complexity via Interactive Protocols}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.12},
  URN =		{urn:nbn:de:0030-drops-201557},
  doi =		{10.4230/LIPIcs.ICALP.2024.12},
  annote =	{Keywords: proof complexity, circuit complexity, interactive protocols}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.24
Exponential Lower Bounds via Exponential Sums

Authors: Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Valiant’s famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. In this paper we study whether, in general, exponential sums (of algebraic circuits) require exponential-size algebraic circuits. We show that the famous Shub-Smale τ-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. Along the way, we also prove an exponential fpt (fixed-parameter tractable) lower bound for the parameterized algebraic complexity class VW⁰_{nb}[𝖯], assuming the same conjecture. VW⁰_{nb}[𝖯] can be thought of as the weighted sums of (unbounded-degree) circuits, where only ± 1 constants are cost-free. To the best of our knowledge, this is the first time the Shub-Smale τ-conjecture has been applied to prove explicit exponential lower bounds. Furthermore, we prove that when this class is fpt, then a variant of the counting hierarchy, namely the linear counting hierarchy collapses. Moreover, if a certain type of parameterized exponential sums is fpt, then integers, as well as polynomials with coefficients being definable in the linear counting hierarchy have subpolynomial τ-complexity. Finally, we characterize a related class VW[𝖥], in terms of permanents, where we consider an exponential sum of algebraic formulas instead of circuits. We show that when we sum over cycle covers that have one long cycle and all other cycles have constant length, then the resulting family of polynomials is complete for VW[𝖥] on certain types of graphs.
Cite as

Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee. Exponential Lower Bounds via Exponential Sums. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.ICALP.2024.24,
  author =	{Bhattacharjee, Somnath and Bl\"{a}ser, Markus and Dutta, Pranjal and Mukherjee, Saswata},
  title =	{{Exponential Lower Bounds via Exponential Sums}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.24},
  URN =		{urn:nbn:de:0030-drops-201677},
  doi =		{10.4230/LIPIcs.ICALP.2024.24},
  annote =	{Keywords: Algebraic complexity, parameterized complexity, exponential sums, counting hierarchy, tau conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.77
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters

Authors: Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). In the graph homomorphism problem, denoted by Hom(H), the graph H is fixed and we need to determine if there exists a homomorphism from an instance graph G to H. We study the complexity of the problem parameterized by the cutwidth of G, i.e., we assume that G is given along with a linear ordering v_1,…,v_n of V(G) such that, for each i ∈ {1,…,n-1}, the number of edges with one endpoint in {v_1,…,v_i} and the other in {v_{i+1},…,v_n} is at most k. We aim, for each H, for algorithms for Hom(H) running in time c_H^k n^𝒪(1) and matching lower bounds that exclude c_H^{k⋅o(1)} n^𝒪(1) or c_H^{k(1-Ω(1))} n^𝒪(1) time algorithms under the (Strong) Exponential Time Hypothesis. In the paper we introduce a new parameter that we call mimsup(H). Our main contribution is strong evidence of a close connection between c_H and mimsup(H): - an information-theoretic argument that the number of states needed in a natural dynamic programming algorithm is at most mimsup(H)^k, - lower bounds that show that for almost all graphs H indeed we have c_H ≥ mimsup(H), assuming the (Strong) Exponential-Time Hypothesis, and - an algorithm with running time exp(𝒪(mimsup(H)⋅k log k)) n^𝒪(1). In the last result we do not need to assume that H is a fixed graph. Thus, as a consequence, we obtain that the problem of deciding whether G admits a homomorphism to H is fixed-parameter tractable, when parameterized by cutwidth of G and mimsup(H). The parameter mimsup(H) can be thought of as the p-th root of the maximum induced matching number in the graph obtained by multiplying p copies of H via a certain graph product, where p tends to infinity. It can also be defined as an asymptotic rank parameter of the adjacency matrix of H. Such parameters play a central role in, among others, algebraic complexity theory and additive combinatorics. Our results tightly link the parameterized complexity of a problem to such an asymptotic matrix parameter for the first time.
Cite as

Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{groenland_et_al:LIPIcs.ICALP.2024.77,
  author =	{Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{77:1--77:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.77},
  URN =		{urn:nbn:de:0030-drops-202208},
  doi =		{10.4230/LIPIcs.ICALP.2024.77},
  annote =	{Keywords: graph homomorphism, cutwidth, asymptotic matrix parameters}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.147
Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games

Authors: Bruno Loff and Mateusz Skomra

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We devise a policy-iteration algorithm for deterministic two-player discounted and mean-payoff games, that runs in polynomial time with high probability, on any input where each payoff is chosen independently from a sufficiently random distribution and the underlying graph of the game is ergodic. This includes the case where an arbitrary set of payoffs has been perturbed by a Gaussian, showing for the first time that deterministic two-player games can be solved efficiently, in the sense of smoothed analysis. More generally, we devise a condition number for deterministic discounted and mean-payoff games played on ergodic graphs, and show that our algorithm runs in time polynomial in this condition number. Our result confirms a previous conjecture of Boros et al., which was claimed as a theorem [Boros et al., 2011] and later retracted [Boros et al., 2018]. It stands in contrast with a recent counter-example by Christ and Yannakakis [Christ and Yannakakis, 2023], showing that Howard’s policy-iteration algorithm does not run in smoothed polynomial time on stochastic single-player mean-payoff games. Our approach is inspired by the analysis of random optimal assignment instances by Frieze and Sorkin [Frieze and Sorkin, 2007], and the analysis of bias-induced policies for mean-payoff games by Akian, Gaubert and Hochart [Akian et al., 2018].
Cite as

Bruno Loff and Mateusz Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{loff_et_al:LIPIcs.ICALP.2024.147,
  author =	{Loff, Bruno and Skomra, Mateusz},
  title =	{{Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{147:1--147:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.147},
  URN =		{urn:nbn:de:0030-drops-202908},
  doi =		{10.4230/LIPIcs.ICALP.2024.147},
  annote =	{Keywords: Mean-payoff games, discounted games, policy iteration, smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.13
Barriers for Recent Methods in Geodesic Optimization

Authors: W. Cole Franks and Philipp Reichenbach

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

Abstract
We study a class of optimization problems including matrix scaling, matrix balancing, multidimensional array scaling, operator scaling, and tensor scaling that arise frequently in theory and in practice. Some of these problems, such as matrix and array scaling, are convex in the Euclidean sense, but others such as operator scaling and tensor scaling are geodesically convex on a different Riemannian manifold. Trust region methods, which include box-constrained Newton’s method, are known to produce high precision solutions very quickly for matrix scaling and matrix balancing (Cohen et. al., FOCS 2017, Allen-Zhu et. al. FOCS 2017), and result in polynomial time algorithms for some geodesically convex problems like operator scaling (Garg et. al. STOC 2018, Bürgisser et. al. FOCS 2019). One is led to ask whether these guarantees also hold for multidimensional array scaling and tensor scaling. We show that this is not the case by exhibiting instances with exponential diameter bound: we construct polynomial-size instances of 3-dimensional array scaling and 3-tensor scaling whose approximate solutions all have doubly exponential condition number. Moreover, we study convex-geometric notions of complexity known as margin and gap, which are used to bound the running times of all existing optimization algorithms for such problems. We show that margin and gap are exponentially small for several problems including array scaling, tensor scaling and polynomial scaling. Our results suggest that it is impossible to prove polynomial running time bounds for tensor scaling based on diameter bounds alone. Therefore, our work motivates the search for analogues of more sophisticated algorithms, such as interior point methods, for geodesically convex optimization that do not rely on polynomial diameter bounds.
Cite as

W. Cole Franks and Philipp Reichenbach. Barriers for Recent Methods in Geodesic Optimization. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 13:1-13:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{franks_et_al:LIPIcs.CCC.2021.13,
  author =	{Franks, W. Cole and Reichenbach, Philipp},
  title =	{{Barriers for Recent Methods in Geodesic Optimization}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{13:1--13:54},
  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.13},
  URN =		{urn:nbn:de:0030-drops-142879},
  doi =		{10.4230/LIPIcs.CCC.2021.13},
  annote =	{Keywords: Geodesically Convex Optimization, Weight Margin, Moment Polytope, Diameter Bounds, Tensor Scaling, Matrix Scaling}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.32
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
DOI: 10.4230/LIPIcs.STACS.2021.1
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
DOI: 10.4230/LIPIcs.ITCS.2018.24
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
DOI: 10.4230/DagRep.5.6.28
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
DOI: 10.4230/DagRep.3.1.47
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
DOI: 10.4230/DagSemProc.10481.1
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
DOI: 10.4230/DagSemProc.10481.2
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
DOI: 10.4230/DagSemProc.06111.12
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}
}
  • Refine by Author
  • 9 Bürgisser, Peter
  • 3 Goldberg, Leslie Ann
  • 3 Jerrum, Mark
  • 3 Walter, Michael
  • 3 Wigderson, Avi
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Algebraic complexity theory
  • 2 Computing methodologies → Algebraic algorithms
  • 2 Theory of computation → Continuous optimization
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 3 Computational complexity
  • 3 constraint satisfaction
  • 3 counting problems
  • 3 geometric complexity theory
  • 3 holographic algorithms
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 6 2024
  • 3 2021
  • 2 2011
  • 1 2006
  • 1 2013
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact