research
∙
08/02/2023
Skolem Meets Bateman-Horn
The Skolem Problem asks to determine whether a given integer linear recu...
share
research
∙
04/27/2023
Multiplicity Problems on Algebraic Series and Context-Free Grammars
In this paper we obtain complexity bounds for computational problems on ...
research
∙
03/16/2023
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
Hypergeometric sequences are rational-valued sequences that satisfy firs...
research
∙
10/12/2022
When are Local Queries Useful for Robust Learning?
Distributional assumptions have been shown to be necessary for the robus...
research
∙
07/04/2022
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
We study the Escape Problem for discrete-time linear dynamical systems o...
research
∙
06/22/2022
What's Decidable about Discrete Linear Dynamical Systems?
We survey the state of the art on the algorithmic analysis of discrete l...
research
∙
05/12/2022
Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks
A fundamental problem in adversarial machine learning is to quantify how...
research
∙
04/28/2022
Skolem Meets Schanuel
The celebrated Skolem-Mahler-Lech Theorem states that the set of zeros o...
research
∙
04/26/2022
The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems
We study fundamental reachability problems on pseudo-orbits of linear dy...
research
∙
02/16/2022
Identity Testing for Radical Expressions
We study the Radical Identity Testing problem (RIT): Given an algebraic ...
research
∙
02/15/2022
The Membership Problem for Hypergeometric Sequences with Rational Parameters
We investigate the Membership Problem for hypergeometric sequences: give...
research
∙
07/05/2021
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
We study the computational complexity of the Escape Problem for discrete...
research
∙
06/03/2021
On the Computation of the Algebraic Closure of Finitely Generated Groups of Matrices
We investigate the complexity of computing the Zariski closure of a fini...
research
∙
06/01/2021
Porous Invariants
We introduce the notion of porous invariants for multipath (or branching...
research
∙
04/21/2021
The Orbit Problem for Parametric Linear Dynamical Systems
We study a parametric version of the Kannan-Lipton Orbit Problem for lin...
research
∙
10/27/2020
Deciding ω-Regular Properties on Linear Recurrence Sequences
We consider the problem of deciding ω-regular properties on infinite tra...
research
∙
07/26/2020
Cyclotomic Identity Testing and Applications
We consider the cyclotomic identity testing (CIT) problem: given a polyn...
research
∙
07/23/2020
On Positivity and Minimality for Second-Order Holonomic Sequences
An infinite sequence ⟨u_n⟩_n∈ℕ of real numbers is holonomic (also known ...
research
∙
07/06/2020
On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems
Consider a discrete dynamical system given by a square matrix M ∈ℚ^d × d...
research
∙
06/12/2020
On the Skolem Problem and Prime Powers
The Skolem Problem asks, given a linear recurrence sequence (u_n), wheth...
research
∙
04/24/2020
Invariants for Continuous Linear Dynamical Systems
Continuous linear dynamical systems are used extensively in mathematics,...
research
∙
09/12/2019
On the Hardness of Robust Classification
It is becoming increasingly important to understand the vulnerability of...
research
∙
07/18/2019
On the Monniaux Problem in Abstract Interpretation
The Monniaux Problem in abstract interpretation asks, roughly speaking, ...
research
∙
02/27/2019
Algebraic Invariants for Linear Hybrid Automata
We exhibit an algorithm to compute the strongest algebraic (or polynomia...
research
∙
02/25/2019
On reachability problems for low dimensional matrix semigroups
We consider the Membership and the Half-space Reachability Problems for ...
research
∙
02/20/2019
Termination of Linear Loops over the Integers
We consider the problem of deciding termination of single-path while loo...
research
∙
02/20/2019
On Termination of Integer Linear Loops
We consider the problem of determining termination of single-path loops ...
research
∙
02/18/2019
Coverability in 1-VASS with Disequality Tests
We show that the control-state reachability problem for one-dimensional ...
research
∙
01/30/2019
The Semialgebraic Orbit Problem
The Semialgebraic Orbit Problem is a fundamental reachability question t...
research
∙
06/20/2018
Effective Divergence Analysis for Linear Recurrence Sequences
We study the growth behaviour of rational linear recurrence sequences. W...
research
∙
03/07/2018
On the Expressiveness and Monitoring of Metric Temporal Logic
It is known that Metric Temporal Logic (MTL) is strictly less expressive...
research
∙
03/05/2018
Costs and Rewards in Priced Timed Automata
We consider Pareto analysis of reachable states of multi-priced timed au...
research
∙
02/26/2018
O-Minimal Invariants for Linear Loops
The termination analysis of linear loops plays a key role in several are...
research
∙
02/19/2018
On the Decidability of Reachability in Linear Time-Invariant Systems
We consider the decidability of state-to-state reachability in linear ti...
research
∙
02/06/2018
Polynomial Invariants for Affine Programs
We exhibit an algorithm to compute the strongest polynomial (or algebrai...
research
∙
11/16/2017
Game Characterization of Probabilistic Bisimilarity, and Applications to Pushdown Automata
We study the bisimilarity problem for probabilistic pushdown automata (p...
research
∙
01/09/2017
