The topological entropy of iterated piecewise affine maps is uncomputable

Autor: Pascal Koiran

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol 4, Iss 2 (2001)

We show that it is impossible to compute (or even to approximate) the topological entropy of a continuous piecewise affine function in dimension four. The same result holds for saturated linear functions in unbounded dimension. We ask whether the top

Externí odkaz: https://doaj.org/article/0ef0e72bdf1a47149c9d7156e0f20bb7

Derandomization and absolute reconstruction for sums of powers of linear forms

Autor: Pascal Koiran, Mateusz Skomra

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, 2021, 887, pp.63-84. ⟨10.1016/j.tcs.2021.07.005⟩
Theoretical Computer Science, Elsevier, 2021, 887, pp.63-84. ⟨10.1016/j.tcs.2021.07.005⟩

We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results we give an algorithm for the following problem: given a homogeneous polynomial of degree 3, decide whether it can be written as a sum

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2be4dfe08a0aa776aac1d0e90aaeec9c
https://hal.laas.fr/hal-03457373

Intersection multiplicity of a sparse curve and a low-degree curve

Autor: Pascal Koiran, Mateusz Skomra

Publikováno v: Journal of Pure and Applied Algebra
Journal of Pure and Applied Algebra, Elsevier, 2020, 224 (7), pp.106279. ⟨10.1016/j.jpaa.2019.106279⟩
Journal of Pure and Applied Algebra, 2020, 224 (7), pp.106279. ⟨10.1016/j.jpaa.2019.106279⟩

Let $F(x, y) \in \mathbb{C}[x,y]$ be a polynomial of degree $d$ and let $G(x,y) \in \mathbb{C}[x,y]$ be a polynomial with $t$ monomials. We want to estimate the maximal multiplicity of a solution of the system $F(x,y) = G(x,y) = 0$. Our main result i

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a4bda0a88eee3b6972fca8bbad4cc681
https://hal.archives-ouvertes.fr/hal-02502580

Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective

Autor: Pascal Koiran

We study orthogonal decompositions of symmetric and ordinary tensors using methods from linear algebra. For the field of real numbers we show that the sets of decomposable tensors can be defined be equations of degree 2. This gives a new proof of som

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::87c4a19deeb15f4f3f0d66cb22c34a5c

On the linear independence of shifted powers

Autor: Ignacio García-Marco, Pascal Koiran, Timothée Pecatte

Publikováno v: Journal of Complexity
Journal of Complexity, 2018, 45, pp.67-82
Journal of Complexity, Elsevier, 2018, 45, pp.67-82

We call shifted power a polynomial of the form $(x-a)^e$. The main goal of this paper is to obtain broadly applicable criteria ensuring that the elements of a finite family $F$ of shifted powers are linearly independent or, failing that, to give a lo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::332db7776aa2be681a8f2b8724c8b8d9
https://hal.science/hal-01520724v2/file/GarciaKoiranPecatte_submission_JCv2.pdf