Fetching the paper…
Reading the bibliography…
It is a long-standing open problem whether there always exists a compression scheme whose size is of the order of the Vapnik-Chervonienkis (VC) dimension $d$.
On the uniform convergence of relative frequencies of events to their probability
V. N. Vapnik and A. Y. Chervonenkis · 1971
Earlier work this paper cites.
On the density of families of sets
N. Sauer · 1972
Earlier work this paper cites.
A combinatorial problem; stability and order for models and theories in infinitary languages
S. Shelah · 1972
Earlier work this paper cites.
A theory of the learnable
L.G. Valiant · 1972
Earlier work this paper cites.
Lopsided sets and orthant-intersection by convex sets
J. Lawrence · 1983
Earlier work this paper cites.
Sous-espaces l 1 n l^{n}_{1} des espaces de banach
A. Pajor · 1985
Earlier work this paper cites.
Relating data compression and learnability
N. Littlestone and M. Warmuth · 1986
Earlier work this paper cites.
Occam’s razor
A. Blumer, A.j Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1987
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989
Earlier work this paper cites.
Reverse Kleitman inequalities
B. Bollobás, A. J. Radcliffe, and Leader I · 1989
Earlier work this paper cites.
Space-bounded learning and the Vapnik-Chervonenkis dimension
S. Floyd · 1989
Earlier work this paper cites.
Learning integer lattices
D. P. Helmbold, R. H. Sloan, and M. K. Warmuth · 1992
Earlier work this paper cites.
Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
B. Gartner and E. Welzl · 1994
Earlier work this paper cites.
Predicting \0,1\-functions on randomly drawn points
D. Haussler, N. Littlestone, and M.K. Warmuth · 1994
Cited alongside, same era.
Defect Sauer results
B. Bollobás and A. J. Radcliffe · 1995
Cited alongside, same era.
Sample compression, learnability, and the Vapnik-Chervonenkis dimension
S. Floyd and M. K. Warmuth · 1995
Cited alongside, same era.
Boosting a weak learning algorithm by majority
Y. Freund · 1995
Cited alongside, same era.
Towards a theory of holistic clustering
A.W.M. Dress · 1997
Cited alongside, same era.
Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
S. Ben-David and A. Litman · 1998
Cited alongside, same era.
Some combinatorial applications of Gröbner bases
L. Rónyai and T. Mészáros · 2011
Later among the works it cites.
Boosting: Foundations and Algorithms
Y. Freund and R. E. Schapire · 2012
Later among the works it cites.
Unpublished results
A. Litman and S. Moran · 2012
Later among the works it cites.
S. Moran · 2012
Later among the works it cites.
A geometric approach to sample compression
B. I. P. Rubinstein and J. H. Rubinstein · 2012
Later among the works it cites.
Externally definable sets and dependent pairs
A. Chernikov and P. Simon · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
G. Greco · 1998
Cited alongside, same era.
Shattering news
R.P. Anstee, L. Rónyai, and A. Sali · 2002
Cited alongside, same era.
Compressing to VC dimension many points
M. K. Warmuth · 2003
Cited alongside, same era.
Combinatorics of lopsided sets
H.J. Bandelt, V. Chepoi, A.W.M. Dress, and J.H. Koolen · 2006
Cited alongside, same era.
Unlabeled compression schemes for maximum classes
D. Kuzmin and M. K. Warmuth · 2007
Cited alongside, same era.
Shifting: One-inclusion mistake bounds and sample compression
B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein · 2008
Cited alongside, same era.
L. Kozma and S. Moran · 2013
Later among the works it cites.
Honest compressions and their application to compression schemes
R. Livni and P. Simon · 2013
Later among the works it cites.
Optimal learners for multiclass problems
A. Daniely and S. Shalev-Shwartz · 2014
Later among the works it cites.
Shattering-extremal set systems of VC dimension at most 2
T. Mészáros and L. Rónyai · 2014
Later among the works it cites.
Generalizing labeled and unlabeled sample compression to multi-label concept classes
R. Samei, B. Yang, and S. Zilles · 2014
Later among the works it cites.
Teaching and compressing for low VC-dimension
S. Moran, A. Shpilka, A. Wigderson, and A. Yehudayoff · 2015
Closest in time.
Sample compression schemes for VC classes
Shay Moran and Amir Yehudayoff · 2016
Closest in time.