4 citations · 20 across the 27 of their papers we have counts for
42 papers
Approximate Polynomial Satisfiability is in the Counting Hierarchy
Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas +1
The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image…
Positivity of Second-Order 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…
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…
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…
Learning Weighted Automata over Number Rings, Concretely and Categorically
Quentin Aristote, Sam van Gool, Daniela Petrişan +1
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted aut…
A parametric version of the Hilbert Nullstellensatz
Rida Ait El Manssour, Nikhil Balaji, Klara Nosan +2
Hilbert's Nullstellensatz is a fundamental result in algebraic geometry that gives a necessary and sufficient condition for a finite collection of multivariate polynomials to have…
Reachability for Multi-Priced Timed Automata with Positive and Negative Rates
Andrew Scoones, Mahsa Shirmohammadi, James Worrell
Multi-priced timed automata (MPTA) are timed automata with observer variables whose derivatives can change from one location to another. Observers are write-only variables, that is…
Simple Linear Loops: Algebraic Invariants and Applications
Rida Ait El Manssour, George Kenison, Mahsa Shirmohammadi +1
The automatic generation of loop invariants is a fundamental challenge in software verification. While this task is undecidable in general, it is decidable for certain restricted c…
Differential Tree Automata
Rida Ait El Manssour, Vincent Cheval, Mahsa Shirmohammadi +1
A rationally dynamically algebraic (RDA) power series is one that arises as (a component of) the solution of a system of differential equations of the form $\boldsymbol{y}' = F(\bo…
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…
Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study 2-player stochastic games on countable graphs. Players Max and Min seek respectively to maximize and minimize the probability of satisfying the game objective. The Büchi o…
Memoryless Strategies in Stochastic Reachability Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study concurrent stochastic reachability games played on finite graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of reaching a set of…
On Learning Polynomial Recursive Programs
Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi +1
We introduce the class of P-finite automata. These are a generalisation of weighted automata, in which the weights of transitions can depend polynomially on the length of the input…
Multiplicity Problems on Algebraic Series and Context-Free Grammars
Nikhil Balaji, Lorenzo Clemente, Klara Nosan +2
In this paper we obtain complexity bounds for computational problems on algebraic power series over several commuting variables. The power series are specified by systems of polyno…
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
George Kenison, Klara Nosan, Mahsa Shirmohammadi +1
Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, a hypergeometric sequence $\langl…
Strategy Complexity of Reachability in Countable Stochastic 2-Player Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study countably infinite stochastic 2-player games with reachability objectives. Our results provide a complete picture of the memory requirements of -optimal (resp…
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,…
The Membership Problem for Hypergeometric Sequences with Rational Parameters
Klara Nosan, Amaury Pouly, Mahsa Shirmohammadi +1
We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence of rational numbers and a target $t \in \math…
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…
Transience in Countable MDPs
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
The Transience objective is not to visit any state infinitely often. While this is not possible in finite Markov Decision Process (MDP), it can be satisfied in countably infinite o…
Strategy Complexity of Parity Objectives in Countable MDPs
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete…
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…
Controlling a Random Population is EXPTIME-hard
Corto Mascle, Mahsa Shirmohammadi, Patrick Totzke
Bertrand et al. [1] (LMCS 2019) describe two-player zero-sum games in which one player tries to achieve a reachability objective in games (on the same finite arena) simultaneou…