14 papers
Positivity of Nearly Linearly Recurrent Sequences
Amaury Pouly, Mahsa Shirmohammadi, James Worrell
Nearly linear recurrences generalise linear recurrences and can be represented as special cases of both linear time-invariant systems in control theory and linear-constraint loops…
Determination Problems for Orbit Closures and Matrix Groups
Rida Ait El Manssour, George Kenison, Mahsa Shirmohammadi +2
Computational problems concerning the orbit of a point under the action of a matrix group occur throughout computer science, including in program analysis, complexity theory, quant…
Algebraic Closure of Matrix Sets Recognized by 1-VASS
Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi +1
It is known how to compute the Zariski closure of a finitely generated monoid of matrices and, more generally, of a set of matrices specified by a regular language. This result was…
On the growth of hypergeometric sequences
George Kenison, Jakub Konieczny, Florian Luca +3
Hypergeometric sequences obey first-order linear recurrence relations with polynomial coefficients and are commonplace throughout the mathematical and computational sciences. For c…
On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
Vincent Cheval, Florian Horn, Soumyajit Paul +1
A major open question in algorithmic game theory is whether normal-form correlated equilibria (NFCE) can be computed efficiently in succinct games such as extensive-form games. Mot…
Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study 2-player zero-sum concurrent (i.e., simultaneous move) stochastic Büchi games and Transience games on countable graphs. Two players, Max and Min, seek respectively to max…