Sign rank versus Vapnik-Chervonenkis dimension
From MaRDI portal
Publication:4610199
DOI10.1070/SM8780MaRDI QIDQ4610199
Noga Alon, Amir Yehudayoff, Shay Moran
Publication date: 6 April 2018
Published in: Sbornik: Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.07648
VC dimensionhyperplane arrangementsign rankhalf-spaceslinear classifiersunbounded-error communication complexity
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Permutations, words, matrices (05A05) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
A Sauer-Shelah-Perles lemma for lattices, Knowledge Graph Completion via Complex Tensor Factorization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- Probabilistic communication complexity
- Communication complexity under product and nonproduct distributions
- The structure of almost all graphs in a hereditary property
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- Halfspace matrices
- \(\epsilon\)-nets and simplex range queries
- Some intersection theorems for ordered sets and graphs
- Eigenvalues and expanders
- On the second eigenvalue of a graph
- Almost tight bounds for \(\epsilon\)-nets
- Localization vs. identification of semi-algebraic sets
- On randomized one-round communication complexity
- Norm-graphs: Variations and applications
- Discrepancy and approximations for bounded VC-dimension
- Intersection graphs of segments
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- Shattering news
- Estimating the optimal margins of embeddings in Euclidean half spaces
- Traces of antichains
- Quasi-optimal range searching in spaces of finite VC-dimension
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Support-vector networks
- Defect Sauer results
- Mnëv's universality theorem revisited
- Combinatorics of lopsided sets
- An algorithmic theory of learning: Robust concepts and random projection
- On the density of families of sets
- Bounding Embeddings of VC Classes into Maximum Classes
- Labeled Compression Schemes for Extremal Classes
- The Sign-Rank of AC$^0$
- Extensions of Lipschitz mappings into a Hilbert space
- Complexity Lower Bounds using Linear Algebra
- Expander graphs and their applications
- Learning Complexity vs Communication Complexity
- A parallel algorithmic version of the local lemma
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- 10.1162/153244303321897681
- Communication Complexity
- Recursive Teaching Dimension, Learning Complexity, and Maximum Classes
- A Geometric Approach to Sample Compression
- Lower Bounds for Approximation by Nonlinear Manifolds
- On Graphs that do not Contain a Thomsen Graph
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
