113 citations · 317 across the 70 of their papers we have counts for
18 papers · 1 filter
On the Complexity of the Skolem Problem at Low Orders
Piotr Bacik, Joël Ouaknine, James Worrell
The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) over the integers has a zero term, that is, whether there e…
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Julian D'Costa, Engel Lefaucheux, Eike Neumann +2
We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for…
Identity Testing for Radical Expressions
Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi +1
We study the Radical Identity Testing problem (RIT): Given an algebraic circuit representing a polynomial and nonnegative integers $a_1, \ldots,…
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
Julian D'Costa, Engel Lefaucheux, Eike Neumann +2
We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for…
On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
Klara Nosan, Amaury Pouly, Sylvain Schmitz +2
We investigate the complexity of computing the Zariski closure of a finitely generated group of matrices. The Zariski closure was previously shown to be computable by Derksen, Jean…
Cyclotomic Identity Testing and Applications
Nikhil Balaji, Sylvain Perifel, Mahsa Shirmohammadi +1
We consider the cyclotomic identity testing (CIT) problem: given a polynomial , decide whether is zero, where i…