26 citations · 42 across the 14 of their papers we have counts for
16 papers
An exponential Lojasiewicz inequality for semi-Pfaffian sets
Nicolai Vorobjov
We prove a generalization of the version, due to A. Gabrielov, of the Łojasiewicz inequality for not necessarily restricted semi-Pfaffian sets. Unlike the most variants of the Łoja…
Partitioning Theorems for Sets of Semi-Pfaffian Sets, with Applications
Martin Lotz, Abhiram Natarajan, Nicolai Vorobjov
We generalize the seminal polynomial partitioning theorems of Guth and Katz to a set of semi-Pfaffian sets. Specifically, given a set of -dimensional s…
Lecture notes on complexity of quantifier elimination over the reals
Nicolai Vorobjov
These are lecture notes for a course I gave in mid-1990s for MSc students at the University of Bath. It presents an algorithm with singly exponential complexity for the existential…
Effective cylindrical cell decompositions for restricted sub-Pfaffian sets
Gal Binyamini, Nicolai Vorobjov
The o-minimal structure generated by the restricted Pfaffian functions, known as restricted sub-Pfaffian sets, admits a natural measure of complexity in terms of a format $\mathcal…
Complexity of deciding whether a tropical linear prevariety is a tropical variety
Dima Grigoriev, Nicolai Vorobjov
We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a…
Upper bounds on Betti numbers of tropical prevarieties
Dima Grigoriev, Nicolai Vorobjov
We prove upper bounds on the sum of Betti numbers of tropical prevarieties in dense and sparse settings. In the dense setting the bound is in terms of the volume of Minkowski sum o…
On irreducible components of real exponential hypersurfaces
Cordian Riener, Nicolai Vorobjov
Fix any algebraic extension of the field of rationals. In this article we study exponential sets . Such sets are described by the vani…
Topological lower bounds for arithmetic networks
Andrei Gabrielov, Nicolai Vorobjov
We prove a complexity lower bound on deciding membership in a semialgebraic set for arithmetic networks in terms of the sum of Betti numbers with respect to "ordinary" (singular) h…
On topological lower bounds for algebraic computation trees
Nicolai Vorobjov, Andrei Gabrielov
We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set is bounded from below (up to a multiplicative constant) by the logarithm o…
Triangulations of monotone families I: Two-dimensional families
Saugata Basu, Andrei Gabrielov, Nicolai Vorobjov
Let be a compact definable set in an o-minimal structure over , e.g., a semi-algebraic or a subanalytic set. A definable family $\{ S_δ|\> 0< δ…
Toric cubes are closed balls
Saugata Basu, Andrei Gabrielov, Nicolai Vorobjov
We prove that toric cubes, which are images of under monomial maps, are the closures of graphs of monotone maps, and in particular semi-algebraically homeomorphic to clos…
A Helly-type theorem for semi-monotone sets and monotone maps
Saugata Basu, Andrei Gabrielov, Nicolai Vorobjov
We consider sets and maps defined over an o-minimal structure over the reals, such as real semi-algebraic or subanalytic sets. A {\em monotone map} is a multi-dimensional generaliz…
Monotone functions and maps
Saugata Basu, Andrei Gabrielov, Nicolai Vorobjov
In [S. Basu, A. Gabrielov, N. Vorobjov, Semi-monotone sets. arXiv:1004.5047v2 (2011)] we defined semi-monotone sets, as open bounded sets, definable in an o-minimal structure over…
Semi-monotone sets
Saugata Basu, Andrei Gabrielov, Nicolai Vorobjov
A coordinate cone in R^n is an intersection of some coordinate hyperplanes and open coordinate half-spaces. A semi-monotone set is a defnable in an o-minimal structure over the rea…
Approximation of definable sets by compact families, and upper bounds on homotopy and homology
Andrei Gabrielov, Nicolai Vorobjov
We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of their approximations by compact o-minimal sets. In particular, we improve the known upper bo…
On the number of homotopy types of fibres of a definable map
Saugata Basu, Nicolai Vorobjov
In this paper we prove a single exponential upper bound on the number of possible homotopy types of the fibres of a Pfaffian map, in terms of the format of its graph. In particular…