Prof Nicolai Vorobjov

Department: Computer Science
Job Title: Professor of Theoretical Computer Science

Telephone: +44 1225 386104
Fax: +44 1225 383493

E-mail Address: masnnvATbath.ac.uk

Postal Address:


Teaching


International workshop Effective Real Analytic Geometry in honour of Andrei Gabrielov at ICMS, Edinburgh

International seminar Complexity of Symbolic and Numerical Problems in honour of Dima Grigoriev at Schloss Dagstuhl


Some recent papers and preprints:


1. Complexity of computations with Pfaffian and Noetherian functions, PDF
by A. Gabrielov and N. Vorobjov, in: Normal Forms, Bifurcations and Finiteness Problems in Differential Equations, 211-250, Kluwer, 2004.


2. Betti numbers of semialgebraic and sub-Pfaffian sets, PDF
by A. Gabrielov, N. Vorobjov, and T. Zell, J. London Math. Soc., 69, part 1, 2004, 27-43.


3. Betti numbers of semialgebraic sets defined by quantifier-free formulae, PDF
by A. Gabrielov and N. Vorobjov, Discrete Comput. Geom., 33, 3, 2005, 395-401.


4. On the number of homotopy types of fibres of a definable map, PDF
by S. Basu and N. Vorobjov, J. London Math. Soc., 76, part 3, 2007, 757-776,


5. Bounds on sizes of finite bisimulations of Pfaffian dynamical systems, PDF
by M. Korovina and N. Vorobjov, Theory Comput. Systems, 43, 2008, 498-515.


6. Approximation of definable sets by compact families, and upper bounds on homotopy and homology, PDF
by A. Gabrielov and N. Vorobjov, J. London Math. Soc., 80, 2, 2009, 35-54.


7. Semi-monotone sets, PDF
by S. Basu, A. Gabrielov, and N. Vorobjov, J. European Math. Soc., 15, 2, 2013, 635-657. DOI 10.4171/JEMS/369


8. Monotone functions and maps, PDF
by S. Basu, A. Gabrielov, and N. Vorobjov, Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas (RACSAM),
107, 1, 2013, 5-33. DOI 10.1007/s13398-012-0076-4


9. A Helly-type theorem for semi-monotone sets and monotone maps, arXiv
by S. Basu, A. Gabrielov, and N. Vorobjov, Discrete and Computational Geometry, 50, 4, 2013, 857-864. DOI 10.1007/s00454-013-9540-y


10. Toric cubes are closed balls, arXiv
by S. Basu, A. Gabrielov, and N. Vorobjov, arXiv:1202.5572.v1 [math.AG] 24 Feb 2012 (this paper is now Section 6 in [8]).


11. Triangulations of monotone families I: two-dimensional families, arXiv
by S. Basu, A. Gabrielov, and N. Vorobjov, Proc. London Math. Soc., 111, 5, 2015, 1013-1051. DOI 10.1112/plms/pdv052


12. On topological lower bounds for algebraic computation trees, PDF
by A. Gabrielov and N. Vorobjov, Foundations of Computational Mathematics, 17, 1, 2017, 61-72. DOI 10.1007/s10208-015-9283-7
View-only version via Springer Nature Sharing


13. Topological lower bounds for arithmetic networks, arXiv
by A. Gabrielov and N. Vorobjov, Computational Complexity, 26, 3, 2017, 687-715. DOI 10.1007/s00037-016-0145-8
View-only version via Springer Nature Sharing


14. On irreducible components of real exponential hypersurfaces, arXiv
by C. Riener and N. Vorobjov, Arnold Mathematical Journal, 3, 3, 2017, 423-443. DOI 10.1007/s40598-017-0073-y
View-only version via Springer Nature Sharing


15. Upper bounds on Betti numbers of tropical prevarieties, arXiv
by D. Grigoriev and N. Vorobjov, Arnold Mathematical Journal, 4, 1, 2018, 127-136. DOI 10.1007/s40598-018-0086-1
View-only version via Springer Nature Sharing


16. Complexity of deciding whether a tropical linear prevariety is a tropical variety, arXiv
by D. Grigoriev and N. Vorobjov, Appl. Algebra Engrg. Comm. Comput., 32, 2, 2021, 157-174. DOI 10.1007/s00200-019-00407-w
Online First
Extended abstract in: CASC 2018, LNCS 11077, 187-196. DOI 10.1007/978-3 -319-99639-4_13
2021 AAECC Best Paper Award


17. Effective cylindrical cell decompositions for restricted sub-Pfaffian sets, arXiv
by G. Binyamini and N. Vorobjov, International Mathematics Research Notices, 2022, 5, 3493-3510. DOI 10.1093/imrn/rnaa285
Article


18. Lecture notes on complexity of quantifier elimination over the reals, arXiv
by N. Vorobjov, arXiv:2112.00456 [math.HO]


List of publications


Non-technical lectures


N N Vorobiev (1925-1995)


A. A. Markov

Naive Set Theory. Notes of lectures given at Leningrad State University, 1947


N. A Shanin

Logic. Notes of lectures given at Leningrad State University, 1977-78


[Department of Computer Science]

[University of Bath]