Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with distribution-independent:
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 >>>

TR19-083 | 4th June 2019
Lior Gishboliner, Asaf Shapira

Testing Graphs against an Unknown Distribution

Revisions: 2

The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property $\mathcal{P}$ is said ... more >>>

ISSN 1433-8092 | Imprint