{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T16:29:53Z","timestamp":1661272193778},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s10208-014-9222-z","type":"journal-article","created":{"date-parts":[[2014,10,27]],"date-time":"2014-10-27T18:10:55Z","timestamp":1414433455000},"page":"199-279","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Complexity Theory of Constructible Functions and Sheaves"],"prefix":"10.1007","volume":"15","author":[{"given":"Saugata","family":"Basu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"9222_CR1","unstructured":"Th\u00e9orie des topos et cohomologie \u00e9tale des sch\u00e9mas. Tome 3. Lecture Notes in Mathematics, Vol. 305. Springer-Verlag, Berlin, 1973. S\u00e9minaire de G\u00e9om\u00e9trie Alg\u00e9brique du Bois-Marie 1963\u20131964 (SGA 4), Dirig\u00e9 par M. Artin, A. Grothendieck et J. L. Verdier. Avec la collaboration de P. Deligne et B. Saint-Donat."},{"key":"9222_CR2","doi-asserted-by":"crossref","unstructured":"D. Abramovich, K. Karu, K. Matsuki, and J. W\u0142odarczyk. Torification and factorization of birational maps. J. Amer. Math. Soc., 15(3):531\u2013572 (electronic), 2002.","DOI":"10.1090\/S0894-0347-02-00396-X"},{"key":"9222_CR3","doi-asserted-by":"crossref","unstructured":"A. I. Barvinok. Feasibility testing for systems of real quadratic equations. Discrete Comput. Geom., 10(1):1\u201313, 1993.","DOI":"10.1007\/BF02573959"},{"key":"9222_CR4","doi-asserted-by":"crossref","unstructured":"Y. Baryshnikov and R. Ghrist. Euler integration over definable functions. Proc. Natl. Acad. Sci. USA, 107(21):9525\u20139530, 2010.","DOI":"10.1073\/pnas.0910927107"},{"key":"9222_CR5","doi-asserted-by":"crossref","unstructured":"S. Basu. On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. Discrete Comput. Geom., 22(1):1\u201318, 1999.","DOI":"10.1007\/PL00009443"},{"key":"9222_CR6","doi-asserted-by":"crossref","unstructured":"S. Basu. Computing the first few Betti numbers of semi-algebraic sets in single exponential time. J. Symbolic Comput., 41(10):1125\u20131154, 2006.","DOI":"10.1016\/j.jsc.2006.07.001"},{"key":"9222_CR7","doi-asserted-by":"crossref","unstructured":"S. Basu. Efficient algorithm for computing the Euler-Poincar\u00e9 characteristic of a semi-algebraic set defined by few quadratic inequalities. Comput. Complexity, 15(3):236\u2013251, 2006.","DOI":"10.1007\/s00037-006-0214-5"},{"key":"9222_CR8","doi-asserted-by":"crossref","unstructured":"S. Basu. Computing the top few Betti numbers of semi-algebraic sets defined by quadratic inequalities in polynomial time. Found. Comput. Math., 8(1):45\u201380, 2008.","DOI":"10.1007\/s10208-005-0208-8"},{"key":"9222_CR9","doi-asserted-by":"crossref","unstructured":"S. Basu. A complex analogue of Toda\u2019s theorem. Found. Comput. Math., 12(3):327\u2013362, 2012.","DOI":"10.1007\/s10208-011-9105-5"},{"key":"9222_CR10","doi-asserted-by":"crossref","unstructured":"S. Basu and M. Kettner. Bounding the number of stable homotopy types of a parametrized family of semi-algebraic sets defined by quadratic inequalities. Proc. London Math. Soc. (3), 98:298\u2013324, 2009.","DOI":"10.1112\/plms\/pdn031"},{"key":"9222_CR11","doi-asserted-by":"crossref","unstructured":"S. Basu, D. V. Pasechnik, and M.-F. Roy. Computing the Betti numbers of semi-algebraic sets defined by partly quadratic sytems of polynomials. J. Algebra, 321(8):2206\u20132229, 2009.","DOI":"10.1016\/j.jalgebra.2008.09.043"},{"key":"9222_CR12","doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack, and M.-F. Roy. On the number of cells defined by a family of polynomials on a variety. Mathematika, 43(1):120\u2013126, 1996.","DOI":"10.1112\/S0025579300011621"},{"key":"9222_CR13","doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack, and M.-F. Roy. Computing the Euler-Poincar\u00e9 characteristics of sign conditions. Comput. Complexity, 14(1):53\u201371, 2005.","DOI":"10.1007\/s00037-005-0190-1"},{"key":"9222_CR14","doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack, and M.-F. Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2006 (second edition).","DOI":"10.1007\/3-540-33099-2"},{"key":"9222_CR15","doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack, and M.-F. Roy. Computing the first Betti number of a semi-algebraic set. Found. Comput. Math., 8(1):97\u2013136, 2008.","DOI":"10.1007\/s10208-007-9001-1"},{"key":"9222_CR16","doi-asserted-by":"crossref","unstructured":"S. Basu and N. Vorobjov. On the number of homotopy types of fibres of a definable map. J. Lond. Math. Soc. (2), 76(3):757\u2013776, 2007.","DOI":"10.1112\/jlms\/jdm069"},{"key":"9222_CR17","doi-asserted-by":"crossref","unstructured":"S. Basu and T. Zell. Polynomial hierarchy, Betti numbers, and a real analogue of Toda\u2019s theorem. Found. Comput. Math., 10(4):429\u2013454, 2010.","DOI":"10.1007\/s10208-010-9062-4"},{"key":"9222_CR18","doi-asserted-by":"crossref","unstructured":"E. Bierstone, D. Grigoriev, P. Milman, and J. Wlodarczyk. Effective Hironaka resolution and its Complexity (with appendix on applications in positive characteristic). ArXiv e-prints, June 2012.","DOI":"10.4310\/AJM.2011.v15.n2.a4"},{"key":"9222_CR19","doi-asserted-by":"crossref","unstructured":"F. Bittner. The universal Euler characteristic for varieties of characteristic zero. Compos. Math., 140(4):1011\u20131032, 2004.","DOI":"10.1112\/S0010437X03000617"},{"key":"9222_CR20","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and real computation. Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"9222_CR21","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. (N.S.), 21(1):1\u201346, 1989."},{"key":"9222_CR22","unstructured":"J. Bochnak, M. Coste, and M.-F. Roy. G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle (Second edition in english: Real Algebraic Geometry), volume 12 (36) of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas] . Springer-Verlag, Berlin, 1987 (1998)."},{"key":"9222_CR23","doi-asserted-by":"crossref","unstructured":"A. Borel et al. Intersection cohomology. Modern Birkh\u00e4user Classics. Birkh\u00e4user Boston Inc., Boston, MA, 2008. Notes on the seminar held at the University of Bern, Bern, 1983, Reprint of the 1984 edition.","DOI":"10.1007\/978-0-8176-4765-0"},{"key":"9222_CR24","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser. Completeness and reduction in algebraic complexity theory, volume 7 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2000.","DOI":"10.1007\/978-3-662-04179-6"},{"key":"9222_CR25","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"9222_CR26","unstructured":"P. B\u00fcrgisser and F. Cucker. Variations by complexity theorists on three themes of Euler, B\u00e9zout, Betti, and Poincar\u00e9. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 73\u2013151. Dept. Math., Seconda Univ. Napoli, Caserta, 2004."},{"key":"9222_CR27","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser and F. Cucker. Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. J. Complexity, 22(2):147\u2013191, 2006.","DOI":"10.1016\/j.jco.2005.11.001"},{"key":"9222_CR28","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, J. M. Landsberg, L. Manivel, and J. Weyman. An overview of mathematical issues arising in the geometric complexity theory approach to VP $$\\ne $$ \u2260 VNP. SIAM J. Comput., 40(4):1179\u20131209, 2011.","DOI":"10.1137\/090765328"},{"key":"9222_CR29","doi-asserted-by":"crossref","unstructured":"R. Cluckers and M. Edmundo. Integration of positive constructible functions against Euler characteristic and dimension. J. Pure Appl. Algebra, 208(2):691\u2013698, 2007.","DOI":"10.1016\/j.jpaa.2006.03.005"},{"key":"9222_CR30","doi-asserted-by":"crossref","unstructured":"R. Cluckers and F. Loeser. Fonctions constructibles et int\u00e9gration motivique. I. C. R. Math. Acad. Sci. Paris, 339(6):411\u2013416, 2004.","DOI":"10.1016\/j.crma.2004.06.026"},{"key":"9222_CR31","doi-asserted-by":"crossref","unstructured":"P. Deligne. \u00c9quations diff\u00e9rentielles \u00e0 points singuliers r\u00e9guliers. Lecture Notes in Mathematics, Vol. 163. Springer-Verlag, Berlin, 1970.","DOI":"10.1007\/BFb0061194"},{"key":"9222_CR32","doi-asserted-by":"crossref","unstructured":"P. Deligne. Th\u00e9orie de Hodge. II.Inst. Hautes \u00c9tudes Sci. Publ. Math., (40):5\u201357, 1971.","DOI":"10.1007\/BF02684692"},{"key":"9222_CR33","doi-asserted-by":"crossref","unstructured":"P. Deligne. Th\u00e9orie de Hodge. III. Inst. Hautes \u00c9tudes Sci. Publ. Math., (44):5\u201377, 1974.","DOI":"10.1007\/BF02685881"},{"key":"9222_CR34","doi-asserted-by":"crossref","unstructured":"P. Deligne. Cohomologie \u00e9tale. Lecture Notes in Mathematics, Vol. 569. Springer-Verlag, Berlin, 1977. S\u00e9minaire de G\u00e9om\u00e9trie Alg\u00e9brique du Bois-Marie SGA 41\u00f8er2, Avec la collaboration de J. F. Boutot, A. Grothendieck, L. Illusie et J. L. Verdier.","DOI":"10.1007\/BFb0091516"},{"key":"9222_CR35","doi-asserted-by":"crossref","unstructured":"A. Dimca. Singularities and topology of hypersurfaces. Universitext. Springer-Verlag, New York, 1992.","DOI":"10.1007\/978-1-4612-4404-2"},{"key":"9222_CR36","doi-asserted-by":"crossref","unstructured":"A. Dimca. Sheaves in topology. Universitext. Springer-Verlag, Berlin, 2004.","DOI":"10.1007\/978-3-642-18868-8"},{"key":"9222_CR37","doi-asserted-by":"crossref","unstructured":"A. Gabrielov and N. Vorobjov. Approximation of definable sets by compact families, and upper bounds on homotopy and homology. J. Lond. Math. Soc. (2), 80(1):35\u201354, 2009.","DOI":"10.1112\/jlms\/jdp006"},{"key":"9222_CR38","doi-asserted-by":"crossref","unstructured":"S. I. Gelfand and Y. I. Manin. Methods of homological algebra. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2003.","DOI":"10.1007\/978-3-662-12492-5"},{"key":"9222_CR39","unstructured":"R. Godement. Topologie alg\u00e9brique et th\u00e9orie des faisceaux. Actualit\u00e9s Sci. Ind. No. 1252. Publ. Math. Univ. Strasbourg. No. 13. Hermann, Paris, 1958."},{"key":"9222_CR40","doi-asserted-by":"crossref","unstructured":"D. Grigoriev. Complexity of deciding Tarski algebra. J. Symbolic Comput., 5(1\u20132):65\u2013108, 1988.","DOI":"10.1016\/S0747-7171(88)80006-3"},{"key":"9222_CR41","doi-asserted-by":"crossref","unstructured":"D. Grigoriev. Constructing double-exponential number of vectors of multiplicities of solutions of polynomial systems. In Symbolic computation: solving equations in algebra, geometry, and engineering (South Hadley, MA, 2000), volume 286 of Contemp. Math., pages 115\u2013120. Amer. Math. Soc., Providence, RI, 2001.","DOI":"10.1090\/conm\/286\/04758"},{"key":"9222_CR42","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and N. Vorobjov. Bounds on numbers of vectors of multiplicities for polynomials which are easy to compute. In Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (St. Andrews), pages 137\u2013145 (electronic). ACM, New York, 2000.","DOI":"10.1145\/345542.345609"},{"key":"9222_CR43","doi-asserted-by":"crossref","unstructured":"R. Hardt. Semi-algebraic local-triviality in semi-algebraic mappings. Amer. J. Math., 102(2):291\u2013302, 1980.","DOI":"10.2307\/2374240"},{"key":"9222_CR44","doi-asserted-by":"crossref","unstructured":"B. Iversen. Cohomology of sheaves. Universitext. Springer-Verlag, Berlin, 1986.","DOI":"10.1007\/978-3-642-82783-9"},{"key":"9222_CR45","doi-asserted-by":"crossref","unstructured":"M. Kashiwara and P. Schapira. Sheaves on manifolds, volume 292 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1990. With a chapter in French by Christian Houzel.","DOI":"10.1007\/978-3-662-02661-8_4"},{"key":"9222_CR46","doi-asserted-by":"crossref","unstructured":"S. Mac Lane and I. Moerdijk. Sheaves in geometry and logic. Universitext. Springer-Verlag, New York, 1994. A first introduction to topos theory, Corrected reprint of the 1992 edition.","DOI":"10.1007\/978-1-4612-0927-0"},{"key":"9222_CR47","unstructured":"C. McCrory and A. Parusi\u0144ski. Algebraically constructible functions: real algebra and topology. In Arc spaces and additive invariants in real algebraic and analytic geometry, volume 24 of Panor. Synth\u00e8ses, pages 69\u201385. Soc. Math. France, Paris, 2007."},{"key":"9222_CR48","doi-asserted-by":"crossref","unstructured":"J. Milnor. On the Betti numbers of real varieties. Proc. Amer. Math. Soc., 15:275\u2013280, 1964.","DOI":"10.1090\/S0002-9939-1964-0161339-9"},{"key":"9222_CR49","doi-asserted-by":"crossref","unstructured":"J. L. Monta\u00f1a, J. E. Morais, and L. M. Pardo. Lower bounds for arithmetic networks. II. Sum of Betti numbers. Appl. Algebra Engrg. Comm. Comput., 7(1):41\u201351, 1996.","DOI":"10.1007\/BF01613615"},{"key":"9222_CR50","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica, 7(1):101\u2013104, 1987.","DOI":"10.1007\/BF02579205"},{"key":"9222_CR51","doi-asserted-by":"crossref","unstructured":"K. D. Mulmuley and M. Sohoni. Geometric complexity theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496\u2013526 (electronic), 2001.","DOI":"10.1137\/S009753970038715X"},{"key":"9222_CR52","unstructured":"C. Peters. Motivic Aspects of Hodge Theory. Tata Institute of Fundamental Research lectures on mathematics. Narosa Publishing House, 2010."},{"key":"9222_CR53","unstructured":"I. G. Petrovski\u012d and O. A. Ole\u012dnik. On the topology of real algebraic surfaces. Izvestiya Akad. Nauk SSSR. Ser. Mat., 13:389\u2013402, 1949."},{"key":"9222_CR54","unstructured":"F. Pham. Singularit\u00e9s des syst\u00e8mes diff\u00e9rentiels de Gauss-Manin, volume 2 of Progress in Mathematics. Birkh\u00e4user Boston, Mass., 1979. With contributions by Lo Kam Chan, Philippe Maisonobe and Jean-\u00c9tienne Rombaldi."},{"key":"9222_CR55","doi-asserted-by":"crossref","unstructured":"J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. I-III. J. Symbolic Comput., 13(3):255\u2013352, 1992.","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"9222_CR56","unstructured":"P. Schapira. Cycles lagrangiens, fonctions constructibles et applications. In S\u00e9minaire sur les \u00c9quations aux D\u00e9riv\u00e9es Partielles, 1988\u20131989, pages Exp. No. XI, 9. \u00c9cole Polytech., Palaiseau, 1989."},{"key":"9222_CR57","doi-asserted-by":"crossref","unstructured":"P. Schapira. Operations on constructible functions. J. Pure Appl. Algebra, 72(1):83\u201393, 1991.","DOI":"10.1016\/0022-4049(91)90131-K"},{"key":"9222_CR58","doi-asserted-by":"crossref","unstructured":"P. Schapira. Constructible functions, Lagrangian cycles and computational geometry. In The Gel\u2019fand Mathematical Seminars, 1990\u20131992, pages 189\u2013202. Birkh\u00e4user Boston, Boston, MA, 1993.","DOI":"10.1007\/978-1-4612-0345-2_12"},{"key":"9222_CR59","doi-asserted-by":"crossref","unstructured":"P. Schapira. Tomography of constructible functions. In Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995), volume 948 of Lecture Notes in Comput. Sci., pages 427\u2013435. Springer, Berlin, 1995.","DOI":"10.1007\/3-540-60114-7_33"},{"key":"9222_CR60","unstructured":"J. Sch\u00fcrmann. Topology of singular spaces and constructible sheaves, volume 63 of Instytut Matematyczny Polskiej Akademii Nauk. Monografie Matematyczne (New Series) [Mathematics Institute of the Polish Academy of Sciences. Mathematical Monographs (New Series)]. Birkh\u00e4user Verlag, Basel, 2003."},{"key":"9222_CR61","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoret. Comput. Sci., 3(1):1\u201322 (1977), 1976.","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"9222_CR62","doi-asserted-by":"crossref","unstructured":"R. Thom. Sur l\u2019homologie des vari\u00e9t\u00e9s alg\u00e9briques r\u00e9elles. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255\u2013265. Princeton Univ. Press, Princeton, N.J., 1965.","DOI":"10.1515\/9781400874842-016"},{"key":"9222_CR63","doi-asserted-by":"crossref","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865\u2013877, 1991.","DOI":"10.1137\/0220053"},{"key":"9222_CR64","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189\u2013201, 1979.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"9222_CR65","unstructured":"L. G. Valiant. Reducibility by algebraic projections. Enseign. Math. (2), 28(3\u20134):253\u2013268, 1982."},{"key":"9222_CR66","unstructured":"L. G. Valiant. An algebraic approach to computational complexity. In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983), pages 1637\u20131643, Warsaw, 1984. PWN."},{"key":"9222_CR67","doi-asserted-by":"crossref","unstructured":"L. van den Dries. Tame topology and o-minimal structures, volume 248 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1998.","DOI":"10.1017\/CBO9780511525919"},{"key":"9222_CR68","doi-asserted-by":"crossref","unstructured":"O. Y. Viro. Some integral calculus based on Euler characteristic. In Topology and geometry\u2013Rohlin Seminar, volume 1346 of Lecture Notes in Math., pages 127\u2013138. Springer, Berlin, 1988.","DOI":"10.1007\/BFb0082775"},{"key":"9222_CR69","unstructured":"A. C.-C. Yao. Decision tree complexity and Betti numbers. J. Comput. System Sci., 55(1, part 1):36\u201343, 1997. 26th Annual ACM Symposium on the Theory of Computing (STOC \u201994) (Montreal, PQ, 1994)."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9222-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-014-9222-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9222-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T05:11:14Z","timestamp":1598418674000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-014-9222-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9222"],"URL":"https:\/\/doi.org\/10.1007\/s10208-014-9222-z","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]}}}