Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with convex optimization:
TR05-103 | 17th August 2005
Leonid Gurvits

A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .
Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that ... 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 >>>

ISSN 1433-8092 | Imprint