ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
On the learnability of Boolean formulae
Full text PdfPdf (1.22 MB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the nineteenth annual ACM symposium on Theory of computing table of contents
New York, New York, United States
Pages: 285 - 295  
Year of Publication: 1987
ISBN:0-89791-221-7
Authors
M. Kearns  Harvard University
M. Li  Harvard University
L. Pitt  University of Illinois
L. Valiant  Harvard University
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 4,   Downloads (12 Months): 35,   Citation Count: 53
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/28395.28426
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
D. Angluin. Learning Regular Sets From Queries and Counterexamples. Technical Report, Yale Universitlt Computer Science Dept., TR-484, 1986.
 
2
D. Angluin and P.D. Laird. Identifying k-CNF Formulas From Noisy Examples. Technical Report, Yale University Computer Science Dept., TR-4 78, 1988.
 
3
D. kngluin and L.G. Valiant. Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings. JCS$, 18(~):155-198, 1979.
4
A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States  [doi>10.1145/12130.12158]
5
M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976  [doi>10.1145/321921.321926]
 
6
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
 
7
D. Haussler. Quantifying the Inductive Bias in Concept Learning. Unpublished manuscript, November, 1986.
 
8
L. Pitt and L.G. Valiant. Computational Limitations on Learning From Examples. Technical Report, Harvard University, TR-05-86, and submitted for publication.
 
9
R. Rivest. Learning Decision-Lists. Unpublished manuscript, December, i986.
10
L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984  [doi>10.1145/1968.1972]
 
11
L. G. Valiant. Learning Disjunctions of Conjunctions. in Proceedings of the 9~h IJCAI, vol. 1, pp 560-566, Los Angeles, CA. August, 1985.
 
12
L. G. Valiant. Deductive Learning. Phil. Trans. R. Soc. Lond. A 312, 441-446, 1984.
13
Avi Wigderson, A new approximate graph coloring algorithm, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.325-329, May 05-07, 1982, San Francisco, California, United States  [doi>10.1145/800070.802207]

CITED BY  53
M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States
Avrim Blum , Prasad Chalasani , Jeffrey Jackson, On learning embedded symmetric concepts, Proceedings of the sixth annual conference on Computational learning theory, p.337-346, July 26-28, 1993, Santa Cruz, California, United States
Funda Ergün , S. Ravi Kumar , Ronitt Rubinfeld, On learning bounded-width branching programs, Proceedings of the eighth annual conference on Computational learning theory, p.361-368, July 05-08, 1995, Santa Cruz, California, United States
Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998
Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States
Scott Evan Decatur, Statistical queries and faulty PAC oracles, Proceedings of the sixth annual conference on Computational learning theory, p.262-268, July 26-28, 1993, Santa Cruz, California, United States
Nader H. Bshouty , Jeffrey C. Jackson, Learning DNF over the uniform distribution using a quantum example oracle, Proceedings of the eighth annual conference on Computational learning theory, p.118-127, July 05-08, 1995, Santa Cruz, California, United States
Howard Aizenstein , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Klaus-Uwe Höffgen , Hans Ulrich Simon, Robust trainability of single neurons, Proceedings of the fifth annual workshop on Computational learning theory, p.428-439, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Rodney G. Downey , Patricia A. Evans , Michael R. Fellows, Parameterized learning complexity, Proceedings of the sixth annual conference on Computational learning theory, p.51-57, July 26-28, 1993, Santa Cruz, California, United States
Philip M. Long, On-line evaluation and prediction using linear functions, Proceedings of the tenth annual conference on Computational learning theory, p.21-31, July 06-09, 1997, Nashville, Tennessee, United States
Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States
Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Michael Kearns , Ming Li , Leslie Valiant, Learning Boolean formulas, Journal of the ACM (JACM), v.41 n.6, p.1298-1328, Nov. 1994
Peter Auer , Philip M. Long , Aravind Srinivasan, Approximating hyper-rectangles: learning and pseudo-random sets, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.314-323, May 04-06, 1997, El Paso, Texas, United States
Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993
Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994
Michele Flammini , Alberto Marchetti-Spaccamela , Luděk Kučera, Learning DNF formulae under classes of probability distributions, Proceedings of the fifth annual workshop on Computational learning theory, p.85-92, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Eyal Kushilevitz , Dan Roth, On learning visual concepts and DNF formulae, Proceedings of the sixth annual conference on Computational learning theory, p.317-326, July 26-28, 1993, Santa Cruz, California, United States
Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
Shankar Vaidyanathan , S. Lakshmivarahan, Analysis of upper bound in Valiant's model for learning bounded CNF expressions, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.754-761, February 14-16, 1993, Indianapolis, Indiana, United States
Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.118-129, July 12-15, 1994, New Brunswick, New Jersey, United States
Lisa Hellerstein , Collette Coullard, Learning binary matroid ports, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.328-335, January 23-25, 1994, Arlington, Virginia, United States
Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States
Yoshifumi Sakai , Akira Maruoka, Learning monotone log-term DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.165-172, July 12-15, 1994, New Brunswick, New Jersey, United States
Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.465-475, May 05-08, 1991, New Orleans, Louisiana, United States
Richard Nock, Complexity in the case against accuracy estimation, Theoretical Computer Science, v.301 n.1-3, p.143-165, 14 May 2003
Judy Goldsmith , Robert H. Sloan, More theory revision with queries (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.441-448, May 21-23, 2000, Portland, Oregon, United States
Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989
Yoshifumi Sakai , Eiji Takimoto , Akira Maruoka, Proper learning algorithm for functions of k terms under smooth distributions, Proceedings of the eighth annual conference on Computational learning theory, p.206-213, July 05-08, 1995, Santa Cruz, California, United States
Naoki Abe, Feasible learnability of formal grammars and the theory of natural language acquisition, Proceedings of the 12th conference on Computational linguistics, p.1-6, August 22-27, 1988, Budapest, Hungry
H. Shvayster, Learnable and Nonlearnable Visual Concepts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.5, p.459-466, May 1990
Judy Goldsmith , Robert H. Sloan , Balázs Szörényi , György Turán, Theory revision with queries: horn, read-once, and parity formulas, Artificial Intelligence, v.156 n.2, p.139-176, July 2004
Haim Shvaytser, Representing knowledge in learning systems by pseudo boolean functions, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
Rocco A. Servedio, On learning monotone DNF under product distributions, Information and Computation, v.193 n.1, p.57-74, 25 August 2004
Russell Greiner , Adam J. Grove , Dan Roth, Learning cost-sensitive active classifiers, Artificial Intelligence, v.139 n.2, p.137-174, August 2002
Peter Auer , Philip M. Long, Structural Results About On-line Learning Models With and Without Queries, Machine Learning, v.36 n.3, p.147-181, Sept. 1999
Bhaskar DasGupta , Hava T. Siegelmann , Eduardo Sontag, On a learnability question associated to neural networks with continuous activations (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.47-56, July 12-15, 1994, New Brunswick, New Jersey, United States
Nader H. Bshouty , Nadav Eiron, Learning monotone dnf from a teacher that almost does not answer membership queries, The Journal of Machine Learning Research, 3, p.49-57, 3/1/2003
Yi Li , Philip M. Long, The Relaxed Online Maximum Margin Algorithm, Machine Learning, v.46 n.1-3, p.361-387, 2002
Vitaly Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Journal of Computer and System Sciences, v.75 n.1, p.13-26, January, 2009
Vitaly Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada
Hai Huang , Wei-Tek Tsai , Yinong Chen, Binary analysis and automated hot patching for Web-based applications, Information and Software Technology, v.48 n.12, p.1148-1158, December, 2006
Richard Nock , Frank Nielsen, Self-improved gaps almost everywhere for the agnostic approximation of monomials, Theoretical Computer Science, v.377 n.1-3, p.139-150, May, 2007
Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, The complexity of properly learning simple concept classes, Journal of Computer and System Sciences, v.74 n.1, p.16-34, February, 2008
Charles H.-P. Wen , Li-C. Wang , Jayanta Bhadra, An incremental learning framework for estimating signal controllability in unit-level verification, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
Eric B. Baum, Review:, Neural Computation, v.1 n.2, p.201-207, Summer 1989
Charles H. -P. Wen , Li-C. Wang , Kwang-Ting Cheng, Simulation-Based Functional Test Generation for Embedded Processors, IEEE Transactions on Computers, v.55 n.11, p.1335-1343, November 2006
Qiong Gao , Ming Li, The minimum description length principle and its application to online learning of handprinted characters, Proceedings of the 11th international joint conference on Artificial intelligence, p.843-848, August 20-25, 1989, Detroit, Michigan
Richard Nock, Inducing interpretable voting classifiers without trading accuracy for simplicity: theoretical results, approximation algorithms, and experiments, Journal of Artificial Intelligence Research, v.17 n.1, p.137-170, July 2002
F. Bergadano, The problem of induction and machine learning, Proceedings of the 12th international joint conference on Artificial intelligence, p.1073-1078, August 24-30, 1991, Sydney, New South Wales, Australia

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
  I.2 ARTIFICIAL INTELLIGENCE


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
M. Kearns: colleagues
M. Li: colleagues
L. Pitt: colleagues
L. Valiant: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player