A dichotomy theorem for learning quantified Boolean formulas

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A dichotomy theorem for learning quantified Boolean formulas

Full text

Pdf (1.24 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the tenth annual conference on Computational learning theory table of contents

Nashville, Tennessee, United States

Pages: 193 - 200

Year of Publication: 1997

ISBN:0-89791-891-6

Author

Víctor Dalmau

Departament LSI, Universitat Politècnica de Catalunya, Campus Nord, Mòdul C5, Jordi Girona Salgado, 1-3, Barcelona 08034, Spain

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 32, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/267460.267496 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	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	2	Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
	3	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Journal of Computer and System Sciences, v.50 n.2, p.336-355, April 1995
	4	Ulf Berggren, Linear time deterministic learning of k-term DNF, Proceedings of the sixth annual conference on Computational learning theory, p.37-40, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168309]
	5	Zhixiang Chen , Steven Homer, On learning counting functions with queries, Proceedings of the seventh annual conference on Computational learning theory, p.218-227, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181116]
	6	Nadia Creignou , Miki Hermann, Complexity of generalized satisfiability counting problems, Information and Computation, v.125 n.1, p.1-12, Feb. 25, 1996 [doi>10.1006/inco.1996.0016]
	7	Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995 [doi>10.1006/jcss.1995.1087]
	8	V. Dalmau. In preparation.
	9	S. Fortune, J. Hopcroft, and J. Wyllie. "The directed subgraph homeomorphism problem" Theor. Comp. Sci., 81(2) (1980), pp. 111-121.
	10	Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
	11	Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
	12	Dimitris Kavvadias , Martha Sideri, The Inverse Satisfiability Problem, Proceedings of the Second Annual International Conference on Computing and Combinatorics, p.250-259, June 17-19, 1996
	13	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 [doi>10.1145/174644.174647]
	14	Sanjeev Khanna , Madhu Sudan , Luca Trevisan, Constraint Satisfaction: The Approximability of Minimization Problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.282, June 24-27, 1997
	15	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
	16	W. Maas and G. Turgm. "On learnability and predicate logic". In Proc. Bar-Ilan Symposium on the Foundations of Artificial Intelligence, BISFAI '95 (1995), pp. 75-85.
	17	C. H. Papadimitriou. "Computational Complexity". Addison- Wesley, (1994).
	18	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	19	Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
	20	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]