Fetching the paper…
Reading the bibliography…
One of the earliest conjectures in computational learning theory-the Sample Compression conjecture-asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension.
Theory of Probability and its Applications 16
Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities · 1971
Earlier work this paper cites.
Journal of Combinatorial Theory, Series A 13
Sauer, N.: On the density of families of sets · 1972
Earlier work this paper cites.
Pacific Journal of Mathematics 41
Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages · 1972
Earlier work this paper cites.
In: SOGC’86, pp. 61–71 (1986)
Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries · 1986
Earlier work this paper cites.
Unpublished manuscript http://www.cse.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf
Littlestone, N., Warmuth, M.: Relating data compression and learnability (1986) · 1986
Earlier work this paper cites.
Unpublished notes
Welzl, E.: Complete range spaces (1987) · 1987
Earlier work this paper cites.
Unpublished notes
Welzl, E., Wöginger, G.: On Vapnik-Chervonenkis dimension one (1987) · 1987
Earlier work this paper cites.
Journal of the ACM 36
Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik-Chervonenkis dimension · 1989
Earlier work this paper cites.
Information and Computation 82
Ehrenfeucht, A., Haussler, D., Kearns, M.J., Valiant, L.G.: A general lower bound on the number of examples needed for learning · 1989
Earlier work this paper cites.
Technical Report TR-89-061, ICSI, UC Berkeley (1989)
Floyd, S.: Space-bounded learning and the Vapnik-Chervonenkis dimension · 1989
Earlier work this paper cites.
In: AAAI’90, pp. 1101–1108 (1990)
Haussler, D.: Probably approximately correct learning · 1990
Earlier work this paper cites.
In: STOC’92, pp. 351–369 (1992)
Angluin, D.: Computational learning theory: survey and selected bibliography · 1992
Earlier work this paper cites.
Information and Computation 115
Haussler, D., Littlestone, N., Warmuth, M.: Predicting { 0 , 1 } \{0,1\} functions on randomly drawn points · 1994
Cited alongside, same era.
ACM Computing Surveys 26
Matoušek, J.: Geometric range searching · 1994
Cited alongside, same era.
Dover (1994)
Trudeau, R.J.: Introduction to Graph Theory · 1994
Cited alongside, same era.
Discrete and Computational Geometry 14
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension · 1995
Cited alongside, same era.
Journal of Combinatorial Theory, Series A 69
Haussler, D.: Sphere packing numbers for subsets of the boolean n n -cube with bounded Vapnik-Chervonenkis dimension · 1995
Cited alongside, same era.
Springer-Verlag (1996)
Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition · 1996
Cited alongside, same era.
Journal of Machine Learning Research 5
von Luxburg, U., Bousquet, O., Schölkopf, B.: A compression approach to support vector model selection · 2004
Later among the works it cites.
Journal of Machine Learning Research 6
Langford, J.: Tutorial on practical prediction theory for classification · 2005
Later among the works it cites.
Neural Information Processing - Letters and Reviews 10
Procaccia, A.D., Rosenschein, J.S.: Exact VC dimension of monotone formulas · 2006
Later among the works it cites.
Journal of Machine Learning Research 8
Kuzmin, D., Warmuth, M.: Unlabeled compression schemes for maximum classes · 2007
Later among the works it cites.
In: COLT’08, pp. 299–310 (2008)
Rubinstein, B.I.P., Rubinstein, J.H.: Geometric & topological representations of maximum classes with applications to sample compression · 2008
Later among the works it cites.
Journal of Computer and System Sciences: Special Issue on Learning Theory 2006 75
Rubinstein, B.I.P., Bartlett, P.L., Rubinstein, J.H.: Shifting: one-inclusion mistake bounds and sample compression · 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
van der Vaart, A.W., Wellner, J.A.: Weak Convergence and Empirical Processes · 1996
Cited alongside, same era.
In: STOC’97, pp. 599–608 (1997)
Kleinberg, J.M.: Two algorithms for nearest-neighbor search in high dimensions · 1997
Cited alongside, same era.
Discrete Applied Mathematics 86
Ben-David, S., Litman, A.: Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes · 1998
Cited alongside, same era.
Cambridge University Press (1999)
Anthony, M., Bartlett, P.L.: Neural Network Learning: Theoretical Foundations · 1999
Cited alongside, same era.
In: COLT’03 (2003)
Warmuth, M.K.: Compressing to VC dimension many points · 2003
Cited alongside, same era.
Later among the works it cites.
In: ALT’10, pp. 209–223 (2010)
Doliwa, T., Simon, H.U., Zilles, S.: Recursive teaching dimension, learning complexity, and maximum classes · 2010
Later among the works it cites.
In: STOC ’10, pp. 409–416 (2010)
Guruswami, V., Hastad, J., Kopparty, S.: On the list-decodability of random linear codes · 2010
Later among the works it cites.
In: ICALP’11, pp. 690–699 (2011)
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms · 2011
Later among the works it cites.
Journal of Machine Learning Research 13
Rubinstein, B.I.P., Rubinstein, J.H.: A geometric approach to sample compression · 2012
Later among the works it cites.
In: COLT’13 (2013)
Livni, R., Simon, P.: Honest compressions and their application to compression schemes · 2013
Later among the works it cites.