Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with evolvability:
TR10-018 | 15th February 2010
Vitaly Feldman

A Complete Characterization of Statistical Query Learning with Applications to Evolvability

Revisions: 1

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity ... more >>>

TR11-089 | 7th June 2011
Paul Valiant

Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions

Revisions: 1

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for ... more >>>

TR11-114 | 8th August 2011
Varun Kanade

Computational Bottlenecks for Evolvability

Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>>

ISSN 1433-8092 | Imprint