Search Results

Documents authored by Koiran, Pascal

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.24
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms

Authors: Pascal Koiran and Subhayan Saha

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomized algorithm for the following problem: If a homogeneous polynomial f ∈ K[x_1 , . . . , x_n] (where K ⊆ ℂ) of degree d is given as a blackbox, decide whether it can be written as a linear combination of d-th powers of linearly independent complex linear forms. The main novel features of the algorithm are: - For d = 3, we improve by a factor of n on the running time from the algorithm in [Pascal Koiran and Mateusz Skomra, 2021]. The price to be paid for this improvement is that the algorithm now has two-sided error. - For d > 3, we provide the first randomized blackbox algorithm for this problem that runs in time poly(n,d) (in an algebraic model where only arithmetic operations and equality tests are allowed). Previous algorithms for this problem [Kayal, 2011] as well as most of the existing reconstruction algorithms for other classes appeal to a polynomial factorization subroutine. This requires extraction of complex polynomial roots at unit cost and in standard models such as the unit-cost RAM or the Turing machine this approach does not yield polynomial time algorithms. - For d > 3, when f has rational coefficients (i.e. K = ℚ), the running time of the blackbox algorithm is polynomial in n,d and the maximal bit size of any coefficient of f. This yields the first algorithm for this problem over ℂ with polynomial running time in the bit model of computation. These results are true even when we replace ℂ by ℝ. We view the problem as a tensor decomposition problem and use linear algebraic methods such as checking the simultaneous diagonalisability of the slices of a tensor. The number of such slices is exponential in d. But surprisingly, we show that after a random change of variables, computing just 3 special slices is enough. We also show that our approach can be extended to the computation of the actual decomposition. In forthcoming work we plan to extend these results to overcomplete decompositions, i.e., decompositions in more than n powers of linear forms.
Cite as

Pascal Koiran and Subhayan Saha. Black Box Absolute Reconstruction for Sums of Powers of Linear Forms. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koiran_et_al:LIPIcs.FSTTCS.2022.24,
  author =	{Koiran, Pascal and Saha, Subhayan},
  title =	{{Black Box Absolute Reconstruction for Sums of Powers of Linear Forms}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.24},
  URN =		{urn:nbn:de:0030-drops-174163},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.24},
  annote =	{Keywords: reconstruction algorithms, tensor decomposition, sums of powers of linear forms, simultaneous diagonalisation, algebraic algorithm, black box}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.37
On the Complexity of Partial Derivatives

Authors: Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.
Cite as

Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the Complexity of Partial Derivatives. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{garciamarco_et_al:LIPIcs.STACS.2017.37,
  author =	{Garcia-Marco, Ignacio and Koiran, Pascal and Pecatte, Timoth\'{e}e and Thomass\'{e}, St\'{e}phan},
  title =	{{On the Complexity of Partial Derivatives}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.37},
  URN =		{urn:nbn:de:0030-drops-69964},
  doi =		{10.4230/LIPIcs.STACS.2017.37},
  annote =	{Keywords: counting complexity, simplicial complex, lower bounds, arithmetic circuits}
}
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/LIPIcs.FSTTCS.2011.127
The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent

Authors: Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related. One of the authors of the present paper has recently proposed a "real tau-conjecture" which is inspired by this connection. The real tau-conjecture states that the number of real roots of a sum of products of sparse univariate polynomials should be polynomially bounded. It implies a superpolynomial lower bound on the size of arithmetic circuits computing the permanent polynomial. In this paper we show that the real tau-conjecture holds true for a restricted class of sums of products of sparse polynomials. This result yields lower bounds for a restricted class of depth-4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.
Cite as

Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki. The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 127-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.FSTTCS.2011.127,
  author =	{Grenet, Bruno and Koiran, Pascal and Portier, Natacha and Strozecki, Yann},
  title =	{{The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{127--139},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.127},
  URN =		{urn:nbn:de:0030-drops-33501},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.127},
  annote =	{Keywords: Algebraic Complexity, Sparse Polynomials, Descartes' Rule of Signs, Lower Bound for the Permanent, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.543
Symmetric Determinantal Representation of Weakly-Skew Circuits

Authors: Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.
Cite as

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier. Symmetric Determinantal Representation of Weakly-Skew Circuits. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 543-554, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.STACS.2011.543,
  author =	{Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha},
  title =	{{Symmetric Determinantal Representation of Weakly-Skew Circuits}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{543--554},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.543},
  URN =		{urn:nbn:de:0030-drops-30426},
  doi =		{10.4230/LIPIcs.STACS.2011.543},
  annote =	{Keywords: algebraic complexity, determinant and permanent of symmetric matrices, formulas, skew circuits, Valiant’s classes}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact