Journal of the ACM Bibliography

Selected papers that cite this one

• Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM, 44(4):616-631, July 1997.

• Svetlana Anoulova, Paul Fischer, Stefan Pölt, and Hans Ulrich Simon. Probably almost Bayes decisions. Information and Computation, 129(1):63-71, 25 August 1996.

• B. Apolloni and S. Chiaravalli. PAC learning of concept classes through the boundaries of their items. Theoretical Computer Science, 172(1-2):91-120, 10 February 1997.

• B. Apolloni and C. Gentile. Sample size lower bounds in PAC learning by Algorithmic Complexity Theory. Theoretical Computer Science, 209(1-2):141-162, 6 December 1998.

• Javed A. Aslam and Scott E. Decatur. On the sample complexity of noise-tolerant learning. Information Processing Letters, 57(4):189-195, 26 February 1996.

• Javed A. Aslam and Scott E. Decatur. Specification and simulation of statistical query algorithms for efficiency and noise tolerance. Journal of Computer and System Sciences, 56(2):191-208, April 1998.

• Javed A. Aslam and Scott E. Decatur. General bounds on statistical query learning and PAC learning with noise via hypothesis boosting. Information and Computation, 141(2):85-118, 15 March 1998.

• Peter Auer and Philip M. Long. Simulating access to hidden information while learning. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 263-272, Montréal, Québec, Canada, 23-25 May 1994.

• Peter Auer, Philip M. Long, and Aravind Srinivasan. Approximating hyper-rectangles: Learning and pseudo-random sets. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 314-323, El Paso, Texas, 4-6 May 1997.

• Peter L. Bartlett and Philip M. Long. Prediction, learning, uniform convergence, and scale-sensitive dimensions. Journal of Computer and System Sciences, 56(2):174-190, April 1998.

• Peter L. Bartlett, Philip M. Long, and Robert C. Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434-452, June 1996.

• Rakesh D. Barve and Philip M. Long. On the complexity of learning from drifting distributions. Information and Computation, 138(2):170-193, 1 November 1997.

• Eric B. Baum. On learning a union of half spaces. Journal of Complexity, 6(1):67-101, March 1990.

• Richard Beigel, Martin Kummer, and Frank Stephan. Quantifying the amount of verboseness. Information and Computation, 118(1):73-90, April 1995.

• Shai Ben-David, Gyora M. Benedek, and Yishay Mansour. A parametrization scheme for classifying models of PAC learnability. Information and Computation, 120(1):11-21, July 1995.

• Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, ..., n}-valued functions. Journal of Computer and System Sciences, 50(1):74-86, February 1995.

• Shai Ben-David and Eli Dichterman. Learning with restricted focus of attention. Journal of Computer and System Sciences, 56(3):277-298, April 1998.

• Shai Ben-David, Alon Itai, and Eyal Kushilevitz. Learning by distances. Information and Computation, 117(2):240-250, March 1995.

• Shai Ben-David and Michael Lindenbaum. Learning distributions by their density levels: A paradigm for learning without a teacher. Journal of Computer and System Sciences, 55(1):171-182, August 1997.

• Avrim Blum, Prasad Chalasani, Sally A. Goldman, and Donna K. Slonim. Learning with unreliable boundary queries. Journal of Computer and System Sciences, 56(2):209-222, April 1998.

• Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 253-262, Montréal, Québec, Canada, 23-25 May 1994.

• Avrim Blum, Lisa Hellerstein, and Nick Littlestone. Learning in the presence of finitely or infinitely many irrelevant attributes. Journal of Computer and System Sciences, 50(1):32-40, February 1995.

• Avrim L. Blum and Ravindran Kannan. Learning an intersection of a constant number of halfspaces over a uniform distribution. Journal of Computer and System Sciences, 54(2):371-380, April 1997.

• Nader H. Bshouty, Sally A. Goldman, and H. David Mathias. Noise-tolerant parallel learning of geometric concepts. Accepted for publication in Information and Computation. Final manuscript received for publication March 17, 1998.

• Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, and Hisao Tamaki. Noise-tolerant distribution-free learning of general geometric concepts. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 151-160, Philadelphia, Pennsylvania, 22-24 May 1996.

• Liming Cai and Jianer Chen. On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences, 54(3):465-474, June 1997.

• John Case, Susanne Kaufmann, Efim Kinber, and Martin Kummer. Learning recursive functions from approximations. Journal of Computer and System Sciences, 55(1):183-196, August 1997.

• Nicolò Cesa-Bianchi, Eli Dichterman, Paul Fischer, and Hans Ulrich Simon. Noise-tolerant learning near the information-theoretic bound. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 141-150, Philadelphia, Pennsylvania, 22-24 May 1996.

• Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427-485, May 1997.

• Zhixiang Chen and Steven Homer. The bounded injury priority method and the learnability of unions of rectangles. Annals of Pure and Applied Logic, 77(2):143-168, 29 January 1996.

• Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, and Kai Werther. On real Turing machines that toss coins. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 335-342, Las Vegas, Nevada, 29 May-1 June 1995.

• Paul Fischer, Klaus-Uwe Höffgen, and Hanno Lefmann. PAC-learning from general examples. Theoretical Computer Science, 172(1-2):43-65, 10 February 1997.

• Lance Fortnow, R\=usi\c{n}\v{s} Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, and Frank Stephan. On the relative sizes of learnable sets. Theoretical Computer Science, 197(1-2):139-156, 15 May 1998.

• Moti Frances and Ami Litman. Optimal mistake bound learning is hard. Information and Computation, 144(1):66-82, 10 July 1998.

• Michael Frazier, Sally Goldman, Nina Mishra, and Leonard Pitt. Learning from a consistently ignorant teacher. Journal of Computer and System Sciences, 52(3):471-492, June 1996.

• Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256-285, September 1995.

• Alan Frieze, Mark Jerrum, and Ravi Kannan. Learning linear transformations. In 37th Annual Symposium on Foundations of Computer Science, pages 359-368, Burlington, Vermont, 14-16 October 1996. IEEE.

• Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50(1):20-31, February 1995.

• Sally A. Goldman, Michael J. Kearns, and Robert E. Schapire. On the sample complexity of weakly learning. Information and Computation, 117(2):276-287, March 1995.

• Sally A. Goldman and H. David Mathias. Teaching a smarter learner. Journal of Computer and System Sciences, 52(2):255-267, April 1996.

• Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. In 37th Annual Symposium on Foundations of Computer Science, pages 339-348, Burlington, Vermont, 14-16 October 1996. IEEE.

• Oded Goldreich and Dana Ron. On universal learning algorithms. Information Processing Letters, 63(3):131-136, 14 August 1997.

• Leonid Gurvits and Pascal Koiran. Approximation and learning of convex superpositions. Journal of Computer and System Sciences, 55(1):161-170, August 1997.

• Thomas Hancock, Tao Jiang, Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Information and Computation, 126(2):114-122, 1 May 1996.

• Susumu Hasegawa, Hiroshi Imai, and Masaki Ishiguro. epsilon-approximations of k-label spaces. Theoretical Computer Science, 137(1):145-157, 9 January 1995.

• David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-150, September 1992.

• D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting {0,1}-functions on randomly drawn points. Information and Computation, 115(2):248-292, December 1994.

• Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, and Dawn Wilkins. How many queries are needed to learn? In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 190-199, Las Vegas, Nevada, 29 May-1 June 1995.

• Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, and Dawn Wilkins. How many queries are needed to learn? Journal of the ACM, 43(5):840-862, September 1996.

• David P. Helmbold and Manfred K. Warmuth. On weak learning. Journal of Computer and System Sciences, 50(3):551-573, June 1995.

• Klaus-U. Höffgen, Hans-U. Simon, and Kevin S. Van Horn. Robust trainability of single neurons. Journal of Computer and System Sciences, 50(1):114-125, February 1995.

• Jeffrey C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414-440, December 1997.

• Mark Jerrum. Simple translation-invariant concepts are hard to learn. Information and Computation, 113(2):300-311, September 1994.

• Tao Jiang and Ming Li. DNA sequencing and string learning. Mathematical Systems Theory, 29(4):387-405, July/August 1996.

• Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. On the learnability of discrete distributions (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 273-282, Montréal, Québec, Canada, 23-25 May 1994.

• Michael Kearns and Leslie Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1):67-95, January 1994.

• J. Kivinen. Learning reliably and with one-sided error. Mathematical Systems Theory, 28(2):141-172, March/April 1995.

• Jyrki Kivinen and Manfred K. Warmuth. Additive versus exponentiated gradient updates for linear prediction. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 209-218, Las Vegas, Nevada, 29 May-1 June 1995.

• Pascal Koiran and Eduardo D. Sontag. Neural networks with quadratic VC dimension. Journal of Computer and System Sciences, 54(1):190-198, February 1997.

• Ilan Kremer, Noam Nissan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 596-605, Las Vegas, Nevada, 29 May-1 June 1995.

• Martin Kummer and Frank Stephan. Recursion theoretic properties of frequency computation and bounded queries. Information and Computation, 120(1):59-77, July 1995.

• Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-261, 1 February 1994.

• Philip M. Long and Manfred K. Warmuth. Composite geometric concepts and polynomial predictability. Information and Computation, 113(2):230-252, September 1994.

• Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets. SIAM Journal on Computing, 26(3):708-732, June 1997.

• Wolfgang Maass and Manfred K. Warmuth. Efficient learning with virtual threshold gates. Information and Computation, 141(1):66-83, 25 February 1998.

• Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Information and Computation, 118(2):316-326, 1 May 1995.

• Ji\v{r}í Matou\v{s}ek. Approximations and optimal geometric divide-and-conquer. Journal of Computer and System Sciences, 50(2):203-208, April 1995.

• Cristopher Moore. Dynamical recognizers: real-time language recognition by analog computers. Theoretical Computer Science, 201(1-2):99-136, 6 July 1998.

• Thomas Natschläger and Michael Schmitt. Exact VC-dimension of Boolean monomials. Information Processing Letters, 59(1):19-20, 8 July 1996.

• Christos H. Papadimitriou and Mihalis Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. Journal of Computer and System Sciences, 53(2):161-170, October 1996.

• Krishnan Pillaipakkamnatt and Vijay Raghavan. Read-twice DNF formulas are properly learnable. Information and Computation, 122(2):236-267, 1 November 1995.

• M. R. K. Krishna Rao. A framework for incremental learning of logic programs. Theoretical Computer Science, 185(1):193-213, 10 October 1997.

• Joel Ratsaby and Vitaly Maiorov. On the value of partial information for learning from examples. Journal of Complexity, 13(4):509-544, December 1997.

• Kathleen Romanik. Approximate testing and its relationship to learning. Theoretical Computer Science, 188(1-2):79-99, 30 November 1997.

• Kathleen Romanik and Jeffrey Scott Vitter. Using Vapnik-Chervonenkis dimension to analyze the testing complexity of program segments. Information and Computation, 128(2):87-108, 1 August 1996.

• Akito Sakurai. On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions. Theoretical Computer Science, 137(1):109-127, 9 January 1995.

• Robert E. Schapire and Linda M. Sellie. Learning sparse multivariate polynomials over a field with queries and counterexamples. Journal of Computer and System Sciences, 52(2):201-213, April 1996.

• John Shawe-Taylor. Sample sizes for threshold networks with equivalences. Information and Computation, 118(1):65-72, April 1995.

• Ayumi Shinohara. Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions. Theoretical Computer Science, 137(1):129-144, 9 January 1995.

• Hans Ulrich Simon. General bounds on the number of examples needed for learning probabilistic concepts. Journal of Computer and System Sciences, 52(2):239-254, April 1996.

• Hans Ulrich Simon. Bounds on the number of examples needed for learning functions. SIAM Journal on Computing, 26(3):751-763, June 1997.

• Jeffrey Scott Vitter and P. Krishnan. Optimal prefetching via data compression. Journal of the ACM, 43(5):771-793, September 1996.

• Jeffrey Scott Vitter and Jyh-Han Lin. Learning in parallel. Information and Computation, 96(2):179-202, February 1992.

• Osamu Watanabe. A framework for polynomial-time query learnability. Mathematical Systems Theory, 27(3):211-229, May/June 1994.

Shortcuts: