loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Conference on Computational Complexity (CCC'06)
Optimal Hardness Results for Maximizing Agreements with Monomials
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
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
Usage of this product signifies your acceptance of the Terms of Use.