Lower Bounds for Approximation by Nonlinear Manifolds

Cites work

Elementary structure of real algebraic varieties
scientific article; zbMATH DE number 3101675 (Why is no real title available?)
Some negative theorems of approximation theory

Cited in

(99)

Dynamical recognizers: real-time language recognition by analog computers
Bounding the number of connected components of a real algebraic set
The complexity of point configurations
The parallel complexity of function approximation
How to find Steiner minimal trees in Euclidean $d$-space
Generalized sum graphs
A combinatorial approach to complexity
The degree of approximation of sets in euclidean space using sets with bounded Vapnik-Chervonenkis dimension
Uniform approximation by neural networks
On best approximation by ridge functions
On the approximation of functional classes equipped with a uniform measure using ridge functions
Irrepresentability of short semilattices by Euclidean subspaces
Some combinatorial-algebraic problems from complexity theory
Stage-graph representations
On the value of partial information for learning from examples
On the number of sets definable by polynomials
An LP-based k-means algorithm for balancing weighted point sets
Implicit representation conjecture for semi-algebraic graphs
Semialgebraic complexity of functions
Embeddings of graphs in Euclidean spaces
Not all graphs are segment $T$-graphs
Density and dimension
The geometry of critical and near-critical values of differentiable mappings
Systems of rational polynomial equations have polynomial size approximate zeros on the average
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
On the number of order types in integer grids of small size
Polyhedral circuits and their applications
Many order types on integer grids of polynomial size
Matrix and tensor rigidity and L_p-approximation
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
Eliminating depth cycles among triangles in three dimensions
On the speed of algebraically defined graph classes
Error bounds for approximations with deep ReLU networks
Robust regression via mutivariate regression depth
Optimizing positional scoring rules for rank aggregation
Weaving patterns of lines and line segments in space
On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations
Study of $D$-decompositions by the methods of computational real-valued algebraic geometry
Counting unique-sink orientations
Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary
The number of disk graphs
Counting dope matrices
Learning bounds for quantum circuits in the agnostic setting
On the number of zero-patterns of a sequence of polynomials
Intersection graphs of L-shapes and segments in the plane
On the complexity of computing and learning with multiplicative neural networks
Counting disk graphs
Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations
Improved enumeration of simple topological graphs
Refined bounds on the number of connected components of sign conditions on a variety
Broadcast transmission to prioritizing receivers
Sign rank versus Vapnik-Chervonenkis dimension
Optimal shooting: Characterizations and applications
Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Distinct distances in the complex plane
Boundedness questions for Calabi-Yau threefolds
On Transversality of Bent Hyperplane Arrangements and the Topological Expressiveness of ReLU Neural Networks
An efficient algorithm for generalized polynomial partitioning and its applications
Sign rank vs discrepancy
Constructive polynomial partitioning for algebraic curves in $\mathbb{R}^3$ with applications
On the complexity of computing a random Boolean function over the reals
Incidences between points and lines in ${\mathbb {R}}^4$
Improved bounds for incidences between points and circles
scientific article; zbMATH DE number 7064043 (Why is no real title available?)
Crossing patterns of segments
VC dimensions of principal component analysis
On the Bochner-Riesz operator in $\mathbb{R}^3$
On the extension complexity of polytopes separating subsets of the Boolean cube
Convex hulls of random order types
Robust subgaussian estimation with VC-dimension
Moduli spaces of geometric graphs
Discrete geometry. Abstracts from the workshop held January 21--26, 2024
A logarithmic bound for simultaneous embeddings of planar graphs
Implicit representation of sparse hereditary families
Inscribable order types
A size-depth trade-off for the analog computation of Boolean functions
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
On the computation of Boolean functions by analog circuits of bounded fan-in
Covariance estimation with direction dependence accuracy
An extension of Warren's lower bounds for approximations
A logarithmic bound for simultaneous embeddings of planar graphs
Sharp lower bounds on interpolation by deep ReLU neural networks at irregularly spaced data
A canonical tree decomposition for order types, and some applications
Turning big data into tiny data: coresets for unsupervised learning problems
Enumeration of intersection graphs of x-monotone curves
Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
Erzeugungsgrad, VC-dimension and neural networks with rational activation function
Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications
Geometric realizations of dichotomous ordinal graphs
The complexity of envy-free graph cutting
Simplices with given 2-face areas
Geometric properties of the ridge function manifold
Approximation of functional compact sets by analytic varieties
Space lower bounds for low-stretch greedy embeddings
Optimal social choice functions: a utilitarian view
The maximum edit distance from hereditary graph properties
Edge intersection graphs of systems of paths on a grid with a bounded number of bends
An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions

This page was built for publication: Lower Bounds for Approximation by Nonlinear Manifolds

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