Resource-Bounded Measure and Learnability

被引：0
|
作者：
W. Lindner
R. Schuler
O. Watanabe
机构：
[1] Abteilung Theoretische Informatik,
[2] Universität Ulm,undefined
[3] 89081 Ulm,undefined
[4] Germany lindner$@informatik.uni-ulm.de,undefined
[5] schuler$@informatik.uni-ulm.de ,undefined
[6] Department of Mathematical and Computing Sciences,undefined
[7] Tokyo Institute of Technology,undefined
[8] Tokyo 152-8552,undefined
[9] Japan watanabe@is.titech.ac.jp,undefined
来源：
Theory of Computing Systems | 2000年 / 33卷
关键词：
Measure Zero; Boolean Circuit; Computable Variant;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider the resource-bounded measure of polynomial-time learnable subclasses of polynomial-size circuits. We show that if EXP ≠ MA, then every PAC-learnable subclass of P/poly has EXP-measure zero. We introduce a nonuniformly computable variant of resource-bounded measure and show that, for every fixed polynomial q , any polynomial-time learnable subclass of circuits of size q has measure zero with respect to P/poly. We relate our results to the question of whether the class of Boolean circuits is polynomial-time learnable.
引用
收藏
页码：151 / 170
页数：19
相关论文
共 50 条
  • [1] Resource-bounded measure and learnability
    Lindner, W
    Schuler, R
    Watanabe, O
    THEORY OF COMPUTING SYSTEMS, 2000, 33 (02) : 151 - 170
  • [2] Resource bounded measure and learnability
    Lindner, W
    Schuler, R
    Watanabe, O
    THIRTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - PROCEEDINGS, 1998, : 261 - 270
  • [3] On pseudorandomness and resource-bounded measure
    Arvind, V
    Köbler, J
    THEORETICAL COMPUTER SCIENCE, 2001, 255 (1-2) : 205 - 221
  • [4] Results on resource-bounded measure
    Buhrman, H
    Fenner, S
    Fortnow, L
    AUTOMATA, LANGUAGES AND PROGRAMMING, 1997, 1256 : 188 - 194
  • [5] A generalization of resource-bounded measure, with an application
    Buhrman, H
    van Melkebeek, D
    Regan, KW
    Sivakumar, D
    Strauss, M
    STACS 98 - 15TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1998, 1373 : 161 - 171
  • [6] Resource-bounded measure (preliminary version)
    Lutz, JH
    THIRTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - PROCEEDINGS, 1998, : 236 - 248
  • [7] Resource-bounded measure on probabilistic classes
    Moser, Philippe
    INFORMATION PROCESSING LETTERS, 2008, 106 (06) : 241 - 245
  • [8] An Outer-Measure Approach for Resource-Bounded Measure
    Jack Jie Dai
    Theory of Computing Systems, 2009, 45 : 64 - 73
  • [9] An Outer-Measure Approach for Resource-Bounded Measure
    Dai, Jack Jie
    THEORY OF COMPUTING SYSTEMS, 2009, 45 (01) : 64 - 73
  • [10] Upward separations and weaker hypotheses in resource-bounded measure
    Harkins, Ryan C.
    Hitchcock, John A.
    THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) : 162 - 171
12345