{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:18Z","timestamp":1725665058998},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632467"},{"type":"electronic","value":"9783540692423"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63246-8_10","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:22:06Z","timestamp":1330280526000},"page":"162-173","source":"Crossref","is-referenced-by-count":1,"title":["Approximating the volume of general Pfaffian bodies"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"Angus","family":"Macintyre","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"10_CR1","unstructured":"M. Anthony and N. Biggs, Computational Learning Theory: An Introduction, Cambridge University Press, 1992."},{"key":"10_CR2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0166-218X(93)90126-9","volume":"47","author":"M. Anthony","year":"1993","unstructured":"M. Anthony and J. Shawe-Taylor, A Result of Vapnik with Applications, Discrete Applied Math. 47 (1993), pp. 207\u2013217.","journal-title":"Discrete Applied Math."},{"key":"10_CR3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1990","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler and M. Warmuth, Learnability and the Vapnik-Chervonenkis Dimension, J. ACM 36 (1990), pp. 929\u2013965.","journal-title":"J. ACM"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"A. Borodin, P. Tiwari, On the Decidability of Sparse Univariate Polynomial Interpolation, Proc. 22nd ACM STOC (1990), pp. 535\u2013545.","DOI":"10.1145\/100216.100292"},{"key":"10_CR5","first-page":"193","volume":"106","author":"F. Delon","year":"1989","unstructured":"F. Delon, D\u00e9finissabilit\u00e9 avec Param\u00e8tres Ext\u00e9rieurs dans Qinp et R, Proc. AMS 106 (1989), pp. 193\u2013198.","journal-title":"Proc. AMS"},{"key":"10_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01389133","volume":"77","author":"J. Denef","year":"1984","unstructured":"J. Denef, The Rationality of the Poincare Series associated to the p-adic Points on a Variety, Invent. Math. 77 (1984), pp. 1\u201323.","journal-title":"Invent. Math."},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"79","DOI":"10.2307\/1971463","volume":"128","author":"J. Denef","year":"1988","unstructured":"J. Denef and L.P.D. van den Dries, p-adic and real subanalytic Sets, Annals of Mathematics 128 (1988), 79\u2013138.","journal-title":"Annals of Mathematics"},{"key":"10_CR8","volume-title":"Tame Topology and o-Minimal Structures","author":"L. Dries van den","year":"1992","unstructured":"L. van den Dries, Tame Topology and o-Minimal Structures, preprint, University of Illinois, Urbana, 1992; to appear as a book."},{"key":"10_CR9","unstructured":"L. van den Dries, D. Haskell, H.D. Macpherson, On Dimensional p-adic Subanalytic Sets, to appear."},{"key":"10_CR10","doi-asserted-by":"crossref","first-page":"183","DOI":"10.2307\/2118545","volume":"140","author":"L. Dries van den","year":"1994","unstructured":"L. van den Dries, A. Macintyre and D. Marker, The Elementary Theory of Restricted Analytic Fields with Exponentation, Annals of Mathematics 140 (1994), pp 183\u2013205.","journal-title":"Annals of Mathematics"},{"key":"10_CR11","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1215\/S0012-7094-96-08416-1","volume":"84","author":"L. Dries van den","year":"1996","unstructured":"L. van den Dries, C. Miller, Geometric Categories and o-Minimal Theories, Duke Journal 84 (1996), 497\u2013540.","journal-title":"Duke Journal"},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1137\/0217060","volume":"17","author":"M. E. Dyer","year":"1988","unstructured":"M. E. Dyer and M. Frieze, On the Complexity of Computing the Volume of a Polyhedron, SIAM J. Comput. 17 (1988), pp. 967\u2013974.","journal-title":"SIAM J. Comput."},{"key":"10_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"83","author":"M. Dyer","year":"1991","unstructured":"M. Dyer, A. Frieze and R. Kannan, A Random Polynomial-Time Algorithm for Approximating the Volume of Convex Bodies, J. ACM 83 (1991), pp. 1\u201317.","journal-title":"J. ACM"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"P. Goldberg and M. Jerrum, Bounding the Vapnik Chervonenkis Dimension of Concept Classes Parametrized by Real Numbers. Machine Learning, 1995. A preliminary version appeared in Proc. 6th ACM Workshop on Computational Learning Theory, pp. 361\u2013369, 1993.","DOI":"10.1145\/168304.168377"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"P. Halmos, Measure Theory, Chelsey-New York, 1950.","DOI":"10.1007\/978-1-4684-9440-2"},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1112\/plms\/s2-10.1.54","volume":"10","author":"G. H. Hardy","year":"1912","unstructured":"G. H. Hardy, Properties of Logarithmic-Exponential Functions, Proc. London Math. Soc. 10 (1912), pp. 54\u201390.","journal-title":"Proc. London Math. Soc."},{"key":"10_CR17","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","volume":"100","author":"D. Haussler","year":"1992","unstructured":"D. Haussler, Decision Theoretic Generalizations of the PAC Model for Neural Net and other Learning Applications, Information and Computation 100, (1992), pp. 78\u2013150.","journal-title":"Information and Computation"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"J. Hertz, A. Krogh and R. G. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, 1991.","DOI":"10.1063\/1.2810360"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"M. W. Hirsch, Differential Topology, Springer-Verlag, 1976.","DOI":"10.1007\/978-1-4684-9449-5"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"M. Karpinski and A. Macintyre, Bounding VC Dimension for Neural Networks: Progress and Prospects (Invited Lecture), Proc. EuroCOLT'95, Lecture Notes in Artificial Intelligence Vol. 904, Springer-Verlag, 1995, pp. 337\u2013341.","DOI":"10.1007\/3-540-59119-2_189"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"M. Karpinski and A. Macintyre, Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks, Proc. 27th ACM STOC (1995), pp. 200\u2013208.","DOI":"10.1145\/225058.225118"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"M. Karpinski and A. Macintyre, Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks, J. Comput. Syst. Sci. 54 (1997), to appear.","DOI":"10.1006\/jcss.1997.1477"},{"key":"10_CR23","unstructured":"M. Karpinski, A. Macintyre, Approximating Volumes and Integrals in o-Minimal and p-Minimal Theories, manuscript in preparation."},{"key":"10_CR24","doi-asserted-by":"crossref","first-page":"1276","DOI":"10.1137\/0222076","volume":"22","author":"M. Karpinski","year":"1993","unstructured":"M. Karpinski and T. Werther, VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions, SIAM J. Computing 22 (1993), pp 1276\u20131285.","journal-title":"SIAM J. Computing"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"A. G. Khovanski, Fewnomials, American Mathematical Society, Providence, R.I., 1991.","DOI":"10.1090\/mmono\/088"},{"key":"10_CR26","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1090\/S0002-9947-1986-0833698-1","volume":"295","author":"J. Knight","year":"1986","unstructured":"J. Knight, A. Pillay and C. Steinhorn, Definable Sets and Ordered Structures II, Trans. American Mathematical Society 295 (1986), pp. 593\u2013605.","journal-title":"Trans. American Mathematical Society"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"P. Koiran, Approximating the Volume of Definable Sets, Proc. 36th IEEE FOCS (1995), pp. 258\u2013265.","DOI":"10.1109\/SFCS.1995.492470"},{"key":"10_CR28","unstructured":"P. Koiran and E. D. Sontag, Neural Networks with Quadratic VC Dimension to appear in Advances in Neural Information Processing Systems (NIPS '95), 1995."},{"key":"10_CR29","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1112\/jlms\/s2-45.2.377","volume":"45","author":"M. C. Laskowski","year":"1992","unstructured":"M. C. Laskowski, Vapnik-Chervonenkis Classes of Definable Sets, J. London Math. Society 45 (1992), pp 377\u2013384.","journal-title":"J. London Math. Society"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"L. Lovasz and M. Simonovits, The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume, Proc. 31 IEEE FOCS (1990), pp. 346\u2013355.","DOI":"10.1109\/FSCS.1990.89553"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"W. Maass, Perspectives of Current Research about the Complexity of Learning on Neural Nets, in: Theoretical Advances in Neural Computation and Learning, V. P. Roychowdhury, K. Y. Siu, A. Orlitsky (Editors), Kluwer Academic Publishers, 1994, pp. 295\u2013336.","DOI":"10.1007\/978-1-4615-2696-4_8"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"W. Maass, Bounds for the Computational Power and Learning Complexity of Analog Neural Nets, Proc. 25th ACM STOC (1993), pp. 335\u2013344.","DOI":"10.1145\/167088.167193"},{"key":"10_CR33","unstructured":"W. Maass, G. Schnitger and E. D. Sontag, On the Computational Power of Sigmoidal versus Boolean Threshold Circuits, Proc. 32nd IEEE FOCS (1991), pp. 767\u2013776."},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"A. J. Macintyre and E. D. Sontag, Finiteness results for Sigmoidal Neural Networks, Proc. 25th ACM STOC (1993), pp. 325\u2013334.","DOI":"10.1145\/167088.167192"},{"key":"10_CR35","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor, On the Betti Numbers of Real Varieties, Proc. of the American Mathematical Society 15 (1964), pp 275\u2013280.","journal-title":"Proc. of the American Mathematical Society"},{"key":"10_CR36","volume-title":"Topology from the Differentiable Viewpoint","author":"J. Milnor","year":"1965","unstructured":"J. Milnor, Topology from the Differentiable Viewpoint, Univ.Press, Virginia, 1965."},{"key":"10_CR37","first-page":"339","volume":"48","author":"B. Pouzat","year":"1983","unstructured":"B. Pouzat, Groupes stables, avec types g\u00e9neriques r\u00e9guliers, J. S. L. 48 (1983), pp. 339\u2013355.","journal-title":"J. S. L."},{"key":"10_CR38","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"3","author":"J. Renegar","year":"1992","unstructured":"J. Renegar, On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Parts I, II, III, J. of Symb. Comput. 3 (1992), pp. 255\u2013352.","journal-title":"Parts I, II, III, J. of Symb. Comput."},{"key":"10_CR39","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1090\/S0002-9904-1942-07811-6","volume":"48","author":"A. Sard","year":"1942","unstructured":"A. Sard, The Measure of the Critical Points of Differentiable Maps, Bull. Amer. Math. Soc. 48 (1942), pp. 883\u2013890.","journal-title":"Bull. Amer. Math. Soc."},{"key":"10_CR40","doi-asserted-by":"crossref","unstructured":"J. Shawe-Taylor, Sample Sizes for Sigmoidal Neural Networks, Preprint, University of London, 1994, to appear in Proc. ACM COLT, 1995.","DOI":"10.1145\/225298.225329"},{"key":"10_CR41","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0022-0000(92)90039-L","volume":"45","author":"E. D. Sontag","year":"1992","unstructured":"E. D. Sontag, Feedforward Nets for Interpolation and Classification, J. Comp. Syst. Sci. 45 (1992), pp. 20\u201348.","journal-title":"J. Comp. Syst. Sci."},{"key":"10_CR42","unstructured":"V. Vapnik, Estimation of Dependencies Based on Empirical Data, Springer Series in Statistics, 1982."},{"key":"10_CR43","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"H. E. Warren","year":"1968","unstructured":"H. E. Warren, Lower Bounds for Approximation by Non-linear Manifolds, Trans. of the AMS 133 (1968), pp. 167\u2013178.","journal-title":"Trans. of the AMS"},{"key":"10_CR44","unstructured":"A. J. Wilkie, Model Completeness Results of Restricted Pfaffian Functions and the Exponential Function; to appear in Journal of the AMS, 1994."},{"key":"10_CR45","unstructured":"A.J. Wilkie, Handwritten manuscript, Oxford 1996."}],"container-title":["Lecture Notes in Computer Science","Structures in Logic and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63246-8_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:17:46Z","timestamp":1605629866000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63246-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632467","9783540692423"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-63246-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}