Article

Free access

On the learnability of Boolean formulae

Authors:

M. Kearns,

M. Li,

L. Pitt,

L. ValiantAuthors Info & Claims

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

Pages 285 - 295

https://doi.org/10.1145/28395.28426

Published: 01 January 1987 Publication History

PDF eReader

References

[1]

D. Angluin. Learning Regular Sets From Queries and Counterexamples. Technical Report, Yale Universitlt Computer Science Dept., TR-484, 1986.

Google Scholar

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

Google Scholar

[3]

D. kngluin and L.G. Valiant. Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings. JCS$, 18(~):155-198, 1979.

Google Scholar

[4]

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Classifying Learnable Geometric Concepts With the V~pnik-Chervonenkis Dimension. In Proceedings of the 18t~' Annual STOC, pp 273-282. Assoc. Cornp. Mach., New York, 1986.

Digital Library

Google Scholar

[5]

M. Garey and D. Johnson. The Complexity of Near-optimal Graph Coloring. J. ACM 23(1):43.49, 1976.

Digital Library

Google Scholar

[6]

M. Garey and D. Johnson. Computers and Intractabilitlt: A Guide to the Theorgt of NP-Compteteness, W. H. Freeman, San Francisco, 1979.

Digital Library

Google Scholar

[7]

D. Haussler. Quantifying the Inductive Bias in Concept Learning. Unpublished manuscript, November, 1986.

Google Scholar

[8]

L. Pitt and L.G. Valiant. Computational Limitations on Learning From Examples. Technical Report, Harvard University, TR-05-86, and submitted for publication.

Google Scholar

[9]

R. Rivest. Learning Decision-Lists. Unpublished manuscript, December, i986.

Google Scholar

[10]

L. G. V~liant. A Theory of the Learnable. Comm. ACM, 27(11):1134-1142, 1984.

Digital Library

Google Scholar

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

Google Scholar

[12]

L. G. Valiant. Deductive Learning. Phil. Trans. R. Soc. Lond. A 312, 441-446, 1984.

Crossref

Google Scholar

[13]

A. Wigderson. A New Approximate Graph Coioring Algorithm. In Proceedings of the 14th Annual $TOC, pp 325-329. Assoc. Comp. Mach., New York, 1982.

Digital Library

Google Scholar

Cited By

View all

Mansour YNock RWilliamson RKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Random classification noise does not defeat all convex potential boosters irrespective of model choiceProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619398(23706-23742)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619398
Beck FFürnkranz JHuynh V(2023)Layerwise Learning of Mixed Conjunctive and Disjunctive Rule SetsRules and Reasoning10.1007/978-3-031-45072-3_7(95-109)Online publication date: 15-Oct-2023
https://doi.org/10.1007/978-3-031-45072-3_7
Lovett SWu KZhang J(2021)Decision List Compression by Mild Random RestrictionsJournal of the ACM10.1145/348500768:6(1-17)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.1145/3485007
Show More Cited By

Index Terms

On the learnability of Boolean formulae

Recommendations

A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiability

We present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSAT_CNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Algorithms for quantified Boolean formulas
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

We present algorithms for solving quantified Boolean formulas (QBF, or sometimes QSAT) with worst case runtime asymptotically less than O(2ⁿ) when the clause-to-variable ratio is smaller or larger than some constant. We solve QBFs in conjunctive normal ...
On the learnability of disjunctive normal form formulas and decision trees

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

January 1987

471 pages

ISBN:0897912217

DOI:10.1145/28395

Editor:
Alfred V. Aho

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC87

Sponsor:

SIGACT

STOC87: 19th Annual ACM Conference on Theory of Computing

New York, New York, USA

Acceptance Rates

STOC '87 Paper Acceptance Rate 50 of 165 submissions, 30%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

160
Total Citations
View Citations
1,568
Total Downloads

Downloads (Last 12 months)671
Downloads (Last 6 weeks)27

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mansour YNock RWilliamson RKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Random classification noise does not defeat all convex potential boosters irrespective of model choiceProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619398(23706-23742)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619398
Beck FFürnkranz JHuynh V(2023)Layerwise Learning of Mixed Conjunctive and Disjunctive Rule SetsRules and Reasoning10.1007/978-3-031-45072-3_7(95-109)Online publication date: 15-Oct-2023
https://doi.org/10.1007/978-3-031-45072-3_7
Lovett SWu KZhang J(2021)Decision List Compression by Mild Random RestrictionsJournal of the ACM10.1145/348500768:6(1-17)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.1145/3485007
Wang YLiu DMa SWu FGao W(2021)Ensemble Learning-Based Rate-Distortion Optimization for End-to-End Image CompressionIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2020.300033131:3(1193-1207)Online publication date: Mar-2021
https://doi.org/10.1109/TCSVT.2020.3000331
Hermo MOzaki A(2020)Exact LearningACM Transactions on Computation Theory10.1145/336993012:1(1-25)Online publication date: 11-Feb-2020
https://dl.acm.org/doi/10.1145/3369930
Lovett SWu KZhang JMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Decision list compression by mild random restrictionsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384241(247-254)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384241
Su GWei DVarshney KMalioutov D(2016)Learning sparse two-level boolean rules2016 IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP)10.1109/MLSP.2016.7738856(1-6)Online publication date: Sep-2016
https://doi.org/10.1109/MLSP.2016.7738856
Qin JYang XFu HLei X(2016)A Novel Nonlinear Algorithm for Area-Wide Near Surface Air Temperature RetrievalIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2016.25367459:7(3283-3296)Online publication date: Jul-2016
https://doi.org/10.1109/JSTARS.2016.2536745
Stevenson ACordy J(2013)Grammatical Inference in Software Engineering: An Overview of the State of the ArtSoftware Language Engineering10.1007/978-3-642-36089-3_12(204-223)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36089-3_12
Gavaldà RThérien D(2009)An algebraic perspective on Boolean function learningProceedings of the 20th international conference on Algorithmic learning theory10.5555/1813231.1813254(201-215)Online publication date: 3-Oct-2009
https://dl.acm.org/doi/10.5555/1813231.1813254
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A satisfiability procedure for quantified boolean formulae

Algorithms for quantified Boolean formulas

On the learnability of disjunctive normal form formulas and decision trees