Paper Info
Title
Learnability of Kolmogorov-easy circuit expressions via queries
Abstract
. Circuit expressions were introduced to provide a natural linkbetween Computational Learning and certain aspects of Structural Complexity.Upper and lower bounds on the learnability of circuit expressionsare known. We study here the case in which the circuit expressions areof low (time-bounded) Kolmogorov complexity. We show that these arepolynomial-time learnable from membership queries in the presence ofan NP oracle. We also exactly characterize the sets that have such circuit...
Year
DOI
Venue
1995
10.1007/3-540-59119-2_172
EuroCOLT
Keywords
Field
DocType
kolmogorov-easy circuit expression,structural complexity,upper and lower bounds
Discrete mathematics,Boolean circuit,Kolmogorov complexity,Expression (mathematics),Computer science,Sequence,Upper and lower bounds,Theoretical computer science,Kolmogorov structure function,Time complexity,Learnability
Conference
ISBN
Citations 
PageRank 
3-540-59119-2
0
0.34
References 
Authors
9
3
Name
Order
Citations
PageRank
José L. Balcázar170162.06
Harry Buhrman21607117.99
Montserrat Hermo35510.77