Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with abduction:
TR18-118 | 20th June 2018
Alexander Durgin, Brendan Juba

Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs

We consider several closely related variants of PAC-learning in which false-positive and false-negative errors are treated differently. In these models we seek to guarantee a given, low rate of false-positive errors and as few false-negative errors as possible given that we meet the false-positive constraint. Bshouty and Burroughs first observed ... more >>>

ISSN 1433-8092 | Imprint