Optimal Hardness Results for Maximizing Agreements with Monomials

Prague, Czech Republic July 16-July 20

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2006.31

21st Annual IEEE Conference on Compu ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Vitaly Feldman

	ASCII Text	x
	Vitaly Feldman, "Optimal Hardness Results for Maximizing Agreements with Monomials," Computational Complexity, Annual IEEE Conference on, pp. 226-236, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.

	BibTex	x
	@article{ 10.1109/CCC.2006.31, author = {Vitaly Feldman}, title = {Optimal Hardness Results for Maximizing Agreements with Monomials}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2006}, issn = {1093-0159}, pages = {226-236}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.31}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Optimal Hardness Results for Maximizing Agreements with Monomials SN - 1093-0159 SP226 EP236 A1 - Vitaly Feldman, PY - 2006 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Vitaly Feldman, Harvard University, USA

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem is motivated by learning of monomials in the agnostic framework of Haussler [12] and Kearns et al. [17]. Finding a monomial with the highest agreement rate was proved to be NP-hard by Kearns and Li [15].

Citation:

Vitaly Feldman, "Optimal Hardness Results for Maximizing Agreements with Monomials," ccc, pp.226-236, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.