Computational Power of Neural Networks: A Kolmogorov Complexity Characterization (2007)
Jos'e Balc'azar, Hava T. Siegelmann
The computational power of recurrent neural networks is shown to depend ultimately on the amount of information encoded in the constants (weights) of the network. The information is characterized by...
Characterizing the Learnability of Kolmogorov Easy Circuit Expressions (2007)
Jos'e Balc'azar, Harry Buhrman
We show that Kolmogorov easy circuit expressions can be learned with membership queries in polynomial time if and only if every NE-predicate is E-solvable. Moreover we show that the previously known...
A Note on Genericity and Bi-Immunity (1995)
Generic sets have all properties (from among a suitably chosen class) that can be enforced by finite extension arguments. In particular, p-generic sets are known to be P-bi-immune. We try to clarify...
A Note on Genericity and Bi-Immunity (1995)
Generic sets have all properties (from among a suitably chosen class) that can be enforced by finite extension arguments. In particular, p-generic sets are known to be P-bi-immune. We try to clarify...
The Structure of Logarithmic Advice Complexity Classes (1992)
Jos'e Balc'azar, Montserrat Hermo
A nonuniform class called here Full-P/log, due to Ko, is studied. It corresponds to polynomial time with logarithmically long advice. Its importance lies in the structural properties it enjoys, more...