Fetching the paper…
Reading the bibliography…
This work studies the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$.
The perceptron–a perceiving and recognizing automaton
Frank Rosenblatt · 1957
Earlier work this paper cites.
On graphs that do not contain a Thomsen graph
William G. Brown · 1966
Earlier work this paper cites.
Lower bounds for approximation by nonlinear manifolds
H. E. Warren · 1968
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. N. Vapnik and A. Ya. Chervonenkis · 1971
Earlier work this paper cites.
On the density of families of sets
Norbert Sauer · 1972
Earlier work this paper cites.
Eigenvalues, expanders and superconcentrators (extended abstract)
Noga Alon and V. D. Milman · 1984
Earlier work this paper cites.
Difference equations, isoperimetric inequality and transience of certain random walks
J. Dodziuk · 1984
Earlier work this paper cites.
Extensions of Lipschitz mapping into Hilbert space
W. B. Johnson and J. Lindenstrauss · 1984
Earlier work this paper cites.
Geometrical realization of set systems and probabilistic communication complexity
Noga Alon, Peter Frankl, and Vojtech Rödl · 1985
Earlier work this paper cites.
λ 1 \lambda_{1} , isoperimetric inequalities for graphs, and superconcentrators
Noga Alon and V. D. Milman · 1985
Earlier work this paper cites.
Eigenvalues and expanders
Noga Alon · 1986
Earlier work this paper cites.
Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory
Noga Alon · 1986
Earlier work this paper cites.
Classifying learnable geometric concepts with the vapnik-chervonenkis dimension (extended abstract)
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth · 1986
Earlier work this paper cites.
Some intersection theorems for ordered sets and graphs
Fan R. K. Chung, Ronald L. Graham, Peter Frankl, and James B. Shearer · 1986
Earlier work this paper cites.
Probabilistic communication complexity
Ramamohan Paturi and Janos Simon · 1986
Earlier work this paper cites.
Partitioning and geometric embedding of range spaces of finite vapnik-chervonenkis dimension
Noga Alon, David Haussler, and Emo Welzl · 1987
Earlier work this paper cites.
epsilon-nets and simplex range queries
David Haussler and Emo Welzl · 1987
Earlier work this paper cites.
Partition trees for triangle counting and other range searching problems
Emo Welzl · 1988
Earlier work this paper cites.
Quasi-optimal range searching in space of finite vc-dimension
Bernard Chazelle and Emo Welzl · 1989
Earlier work this paper cites.
Traces of antichains
Peter Frankl · 1989
Earlier work this paper cites.
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
N. E. Mnev · 1989
Earlier work this paper cites.
Stretchabilltv of pseudolines is np-hard
Peter W. Shor · 1990
Earlier work this paper cites.
A parallel algorithmic version of the local lemma
Noga Alon · 1991
Earlier work this paper cites.
On the second eigenvalue of a graph
A. Nilli · 1991
Cited alongside, same era.
A training algorithm for optimal margin classifiers
Bernhard E. Boser, Isabelle Guyon, and Vladimir Vapnik · 1992
Cited alongside, same era.
Almost tight bounds for epsilon-nets
János Komlós, János Pach, and Gerhard J. Woeginger · 1992
Cited alongside, same era.
Discrepancy and approximations for bounded vc-dimension
Jirí Matousek, Emo Welzl, and Lorenz Wernisch · 1993
Cited alongside, same era.
Vapnik-chervonenkis dimension and (pseudo-)hyperplane arrangements
Bernd Gärtner and Emo Welzl · 1994
Cited alongside, same era.
Defect sauer results
Béla Bollobás and A. J. Radcliffe · 1995
Cited alongside, same era.
Support-vector networks
An algorithmic theory of learning: Robust concepts and random projection
Rosa I. Arriaga and Santosh Vempala · 2006
Later among the works it cites.
Combinatorics of lopsided sets
Hans-Jürgen Bandelt, Victor Chepoi, Andreas W. M. Dress, and Jack H. Koolen · 2006
Later among the works it cites.
On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
Jürgen Forster and Hans-Ulrich Simon · 2006
Later among the works it cites.
Expander graphs and their applications
Shlomo Hoory, Nathan Linial, and Avi Wigderson · 2006
Later among the works it cites.
Unlabeled compression schemes for maximum classes
Dima Kuzmin and Manfred K. Warmuth · 2007
Later among the works it cites.
Halfspace matrices
Alexander A. Sherstov · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Corinna Cortes and Vladimir Vapnik · 1995
Cited alongside, same era.
Sample compression, learnability, and the vapnik-chervonenkis dimension
Sally Floyd and Manfred K. Warmuth · 1995
Cited alongside, same era.
Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension
David Haussler · 1995
Cited alongside, same era.
Mnëv’s universality theorem revisited
J. Richter-Gebert · 1995
Cited alongside, same era.
Communication complexity
Eyal Kushilevitz and Noam Nisan · 1997
Cited alongside, same era.
Localization vs. identification of semi-algebraic sets
Shai Ben-David and Michael Lindenbaum · 1998
Cited alongside, same era.
Visibility constraints on features of 3d objects
Ronen Basri, Pedro F. Felzenszwalb, Ross B. Girshick, David W. Jacobs, and Caroline J. Klivans · 2009
Later among the works it cites.
An approximation algorithm for approximation rank
Troy Lee and Adi Shraibman · 2009
Later among the works it cites.
Learning complexity vs communication complexity
Nathan Linial and Adi Shraibman · 2009
Later among the works it cites.
Complexity lower bounds using linear algebra
Satyanarayana V. Lokam · 2009
Later among the works it cites.
Recursive teaching dimension, learning complexity, and maximum classes
Thorsten Doliwa, Hans-Ulrich Simon, and Sandra Zilles · 2010
Later among the works it cites.
The sign-rank of ac 0 {}^{\mbox{0}}
Alexander A. Razborov and Alexander A. Sherstov · 2010
Later among the works it cites.
Communication complexity under product and nonproduct distributions
Alexander A. Sherstov · 2010
Later among the works it cites.
The structure of almost all graphs in a hereditary property
Noga Alon, József Balogh, Béla Bollobás, and Robert Morris · 2011
Later among the works it cites.
Shay Moran · 2012
Later among the works it cites.
A geometric approach to sample compression
Benjamin I. P. Rubinstein and J. Hyam Rubinstein · 2012
Later among the works it cites.
Recursive teaching dimension, vc-dimension and sample compression
Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles · 2014
Later among the works it cites.
The existence of designs
P. Keevash · 2014
Later among the works it cites.
Intersection graphs of segments and $\exists\mathbb{R}$
Jirí Matousek · 2014
Later among the works it cites.
Bounding embeddings of VC classes into maximum classes
J. Hyam Rubinstein, Benjamin I. P. Rubinstein, and Peter L. Bartlett · 2014
Later among the works it cites.
The complexity of computing the minimum rank of a sign pattern matrix
Amey Bhangale and Swastik Kopparty · 2015
Closest in time.
Labeled compression schemes for extremal classes
Shay Moran and Manfred K. Warmuth · 2015
Closest in time.