Journal of the ACM Bibliography
Leonard Pitt and Leslie G. Valiant.
Computational limitations on learning from examples. Journal of
the ACM, 35(4):965-984, October 1988.
[BibTeX entry]
Selected papers that cite this one
- Dana Angluin, Lisa Hellerstein, and Marek Karpinski. Learning read-once formulas with
queries. Journal of the ACM, 40(1):185-210, January
1993.
- Hiroki Arimura, Hiroki Ishizaka, and Takeshi Shinohara. Learning unions of tree
patterns using queries. Theoretical Computer Science,
185(1):47-62, 10 October 1997.
- 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.
- 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 and Steven Rudich. Fast learning of
k-term DNF formulas with queries. Journal of
Computer and System Sciences, 51(3):367-373, December 1995.
- Endre Boros, Toshihide Ibaraki, and Kazuhisa Makino. Error-free and best-fit extensions
of partially defined Boolean functions. Information and
Computation, 140(2):254-283, 1 February 1998.
- Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan,
and Christino Tamon. Oracles and queries
that are sufficient for exact learning. Journal of Computer
and System Sciences, 52(3):421-433, June 1996.
- William J. Bultman and Wolfgang Maass. Fast identification of geometric
objects with membership queries. Information and
Computation, 118(1):48-64, April 1995.
- 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.
- Thomas Eiter, Toshihide Ibaraki, and Kazuhisa Makino. Double Horn functions.
Information and Computation, 144(2):155-190, 1 August 1998.
- Shao C. Fang and Santosh S. Venkatesh. Learning binary
perceptrons perfectly efficiently. Journal of Computer and
System Sciences, 52(2):374-389, April 1996.
- Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E.
Schapire, and Linda Sellie. Efficient learning of typical
finite automata from random walks. Information and
Computation, 138(1):23-48, 10 October 1997.
- 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.
- 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.
- 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.
- 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.
- 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.
- Mark Jerrum. Simple
translation-invariant concepts are hard to learn. Information
and Computation, 113(2):300-311, September 1994.
- Michael Kearns, Ming Li, and Leslie Valiant. Learning Boolean formulas.
Journal of the ACM, 41(6):1298-1328, November 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.
- Ludek Kucera, Alberto Marchetti-Spaccamela, and Marco Protasi. On learning monotone DNF formulae
under uniform distributions. Information and
Computation, 110(1):84-95, April 1994.
- Steffen Lange, Thomas Zeugmann, and Shyam Kapur. Monotonic and dual
monotonic language learning. Theoretical Computer
Science, 155(2):365-410, 11 March 1996.
- Philip M. Long and Manfred K. Warmuth. Composite geometric concepts and
polynomial predictability. Information and Computation,
113(2):230-252, September 1994.
- Yishay Mansour. An
O(n^{log log n}) learning algorithm for
DNF under the uniform distribution. Journal of Computer and
System Sciences, 50(3):543-550, June 1995.
- Andrew T. Ogielski. Minimal samples of positive
examples identifying k-CNF Boolean functions.
Information and Computation, 113(2):220-229, September
1994.
- Leonard Pitt and Manfred K. Warmuth. The minimum consistent DFA problem
cannot be approximated within any polynomial. Journal of the
ACM, 40(1):95-142, January 1993.
- Ronald L. Rivest and Robert Sloan. A formal model of hierarchical
concept learning. Information and Computation,
114(1):88-114, October 1994.
- Yoshifumi Sakai, Eiji Takimoto, and Akira Maruoka. Proper learning algorithm for functions of
k terms under smooth distributions. Accepted for
publication in Information and Computation. Final manuscript
received for publication November 30, 1998.
- Shinichi Shimozono, Kouichi Hirata, and Ayumi Shinohara. On the hardness of
approximating the minimum consistent acyclic DFA and decision
diagram. Information Processing Letters, 66(4):165-170,
29 May 1998.
- Osamu Watanabe. A framework for
polynomial-time query learnability. Mathematical Systems
Theory, 27(3):211-229, May/June 1994.
- Thomas Zeugmann, Steffen Lange, and Shyam Kapur. Characterizations of monotonic
and dual monotonic language learning. Information and
Computation, 120(2):155-173, 1 August 1995.
Shortcuts: