Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR04-068 | 13th August 2004
Nir Ailon, Bernard Chazelle

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>


TR04-067 | 20th July 2004
hadi salmasian, ravindran kannan, Santosh Vempala

The Spectral Method for Mixture Models

We present an algorithm for learning a mixture of distributions.
The algorithm is based on spectral projection and
is efficient when the components of the mixture are logconcave
distributions.

more >>>

TR04-066 | 6th July 2004
Tomoyuki Yamakami, Toshio Suzuki

Resource Bounded Immunity and Simplicity

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint