Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations

DOI10.1007/978-3-540-75225-7_12zbMath1142.68380OpenAlexW1921526413MaRDI QIDQ3520053

Cesar Alonso, José Luis 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

parallel computationconcept learningVapnik-Chervonenkis dimensionformula sizeMilnor-Thom bounds

Mathematics Subject Classification ID

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

Cites Work

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

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