Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations

DOI10.1007/978-3-540-75225-7_12MaRDI QIDQ3520053zbMATH OpenOpenAlexFDO

Authors Cesar Alonso, J. L. Montaña

Publication date 19 August 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75225-7_12

zbMATH Keywords

concept learningformula sizeMilnor-Thom boundsparallel computationVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

Computational learning theory (68Q32) Parallel algorithms in computer science (68W10) Symbolic computation and algebraic computation (68W30)

Recommendations

• On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• VC Dimension Bounds for Analytic Algebraic Computations
• Learnability and the Vapnik-Chervonenkis dimension
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions

Cites work

• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• An extension of Warren's lower bounds for approximations
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity of deciding Tarski algebra
• scientific article; zbMATH DE number 16658 (Why is no real title available?)
• scientific article; zbMATH DE number 1222560 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 3999284 (Why is no real title available?)
• Lower Bounds for Approximation by Nonlinear Manifolds
• Lower bounds for arithmetic networks
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Betti Numbers of Real Varieties
• Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
• Proving simultaneous positivity of linear forms
• Time-space tradeoffs in algebraic complexity theory

Cited in

(5)

• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations
• Estimate of a VCD image of a \(k\)-parametric template \(t = t[+,\cdot]\).
• VC Dimension Bounds for Analytic Algebraic Computations
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions

This page was built for publication: Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3520053)