Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Semialgebraic Orbit Problem
180
0
0.0
(
0
)
Added by
Shaull Almagor
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Semialgebraic Orbit Problem is a fundamental reachability question that arises in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurrence sequences, and linear while loops. An instance of the problem comprises a dimension $dinmathbb{N}$, a square matrix $Ainmathbb{Q}^{dtimes d}$, and semialgebraic source and target sets $S,Tsubseteq mathbb{R}^d$. The question is whether there exists $xin S$ and $ninmathbb{N}$ such that $A^nx in T$. The main result of this paper is that the Semialgebraic Orbit Problem is decidable for dimension $dleq 3$. Our decision procedure relies on separation bounds for algebraic numbers as well as a classical result of transcendental number theory---Bakers theorem on linear forms in logarithms of algebraic numbers. We moreover argue that our main result represents a natural limit to what can be decided (with respect to reachability) about the orbit of a single matrix. On the one hand, semialgebraic sets are arguably the largest general class of subsets of $mathbb{R}^d$ for which membership is decidable. On the other hand, previous work has shown that in dimension $d=4$, giving a decision procedure for the special case of the Orbit Problem with singleton source set $S$ and polytope target set $T$ would entail major breakthroughs in Diophantine approximation.
rate research
Read More
The emph{Orbit Problem} consists of determining, given a linear transformation $A$ on $mathbb{Q}^d$, together with vectors $x$ and $y$, whether the orbit of $x$ under repeated applications of $A$ can ever reach $y$. This problem was famously shown to be decidable by Kannan and Lipton in the 1980s. In this paper, we are concerned with the problem of synthesising suitable emph{invariants} $mathcal{P} subseteq mathbb{R}^d$, emph{i.e.}, sets that are stable under $A$ and contain $x$ and not $y$, thereby providing compact and versatile certificates of non-reachability. We show that whether a given instance of the Orbit Problem admits a semialgebraic invariant is decidable, and moreover in positive instances we provide an algorithm to synthesise suitable invariants of polynomial size. It is worth noting that the existence of emph{semilinear} invariants, on the other hand, is (to the best of our knowledge) not known to be decidable.
Semialgebraic splines are functions that are piecewise polynomial with respect to a cell decomposition into sets defined by polynomial inequalities. We study bivariate semialgebraic splines, formulating spaces of semialgebraic splines in terms of graded modules. We compute the dimension of the space of splines with large degree in two extreme cases when the cell decomposition has a single interior vertex. First, when the forms defining the edges span a two-dimensional space of forms of degree n---then the curves they define meet in n^2 points in the complex projective plane. In the other extreme, the curves have distinct slopes at the vertex and do not simultaneously vanish at any other point. We also study examples of the Hilbert function and polynomial in cases of a single vertex where the curves do not satisfy either of these extremes.
We prove that the exa
Set disjointness is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including $-$ most famously $-$ interactive randomised communication with bounded error, the problem requires much communication. In this work we were looking for a variation of the set disjointness problem, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection.
It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is $log$-complete in $Pi_2^p$. It had been shown quite recently that already the containment problem for multi-dimensional linear sets is $log$-complete in $Pi_2^p$ (where hardness even holds for a unary encoding of the numerical input parameters). In this paper, we show that already the containment problem for $1$-dimensional linear sets (with binary encoding of the numerical input parameters) is $log$-hard (and therefore also $log$-complete) in $Pi_2^p$. However, combining both restrictions (dimension $1$ and unary encoding), the problem becomes solvable in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
