M. Kearns
M. Li
L. Valiant
- 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. Google ScholarDigital Library
- 5.M. Garey and D. Johnson. The Complexity of Near-optimal Graph Coloring. J. ACM 23(1):43.49, 1976. Google ScholarDigital Library
- 6.M. Garey and D. Johnson. Computers and Intractabilitlt: A Guide to the Theorgt of NP-Compteteness, W. H. Freeman, San Francisco, 1979. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
Index Terms
- On the learnability of Boolean formulae
Recommendations
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiabilityWe present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSATCNF 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 algorithmsWe present algorithms for solving quantified Boolean formulas (QBF, or sometimes QSAT) with worst case runtime asymptotically less than O(2n) when the clause-to-variable ratio is smaller or larger than some constant. We solve QBFs in conjunctive normal ...
Comments