Journal of the ACM Bibliography

Selected papers that cite this one

• Edoardo Amaldi and Viggo Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(1-2):237-260, 6 December 1998.

• Dana Angluin and Michael Kharitonov. When won't membership queries help? Journal of Computer and System Sciences, 50(2):336-355, April 1995.

• 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.

• Carlos Domingo, Tatsuie Tsukiji, and Osamu Watanabe. Partial Occam's Razor and its applications. Information Processing Letters, 64(4):179-185, 28 November 1997.

• 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.

• 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.

• 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.

• Michael Kearns and Yishay Mansour. On the boosting ability of top-down decision tree learning algorithms. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 459-468, Philadelphia, Pennsylvania, 22-24 May 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.

• Moni Naor. Evaluation may be easier than generation (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 74-83, Philadelphia, Pennsylvania, 22-24 May 1996.

• Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 458-467, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Pekka Orponen. Neural networks and complexity theory. Nordic Journal of Computing, 1(1):94-110, Spring 1994.

• Ronald L. Rivest and Robert E. Schapire. Diversity-based inference of finite automata. Journal of the ACM, 41(3):555-589, May 1994.

Selected references

• Leonard Adleman, Kenneth Manders, and Gary Miller. On taking roots in finite fields. In 18th Annual Symposium on Foundations of Computer Science, pages 175-178, Providence, Rhode Island, 31 October-2 November 1977. IEEE.

• Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87-106, November 1987.

• Dana Angluin and Michael Kharitonov. When won't membership queries help? (extended abstract). In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 444-454, New Orleans, Louisiana, 6-8 May 1991.

• Avrim Blum. An \tilde{O}(n^{0.4})-approximation algorithm for 3-coloring (and improved approximation algorithm for k-coloring). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 535-542, Seattle, Washington, 15-17 May 1989.

• Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, October 1989.

• E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302-320, June 1978.

• Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, October 1986.

• Michael Kearns, Ming Li, Leonard Pitt, and Leslie Valiant. On the learnability of Boolean formulae. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 285-295, New York City, 25-27 May 1987.

• Leonid A. Levin. One-way functions and pseudorandom generators. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 363-365, Providence, Rhode Island, 6-8 May 1985.

• Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35(4):965-984, October 1988.

• Leonard Pitt and Manfred K. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 421-432, Seattle, Washington, 15-17 May 1989.

• Robert E. Schapire. The strength of weak learnability (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 28-33, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Avi Wigderson. A new approximate graph coloring algorithm. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 325-329, San Francisco, California, 5-7 May 1982.

• Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 November 1982. IEEE.

Shortcuts: