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-071 | 11th August 2004
Marcus Schaefer, Stephen A. Fenner

Simplicity and Strong Reductions

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>


TR04-070 | 22nd June 2004
Leonid Gurvits

Combinatorial and algorithmic aspects of hyperbolic polynomials

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$
be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.
The support of such polynomial $p(x_1,...,x_n)$
is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ... more >>>


TR04-069 | 13th August 2004
Eran Rom, Amnon Ta-Shma

Improving the alphabet size in high noise, almost optimal rate list decodable codes

Revisions: 2

In this note we revisit the construction of high noise, almost
optimal rate list decodable code of Guruswami ("Better extractors for better codes?")
Guruswami showed that based on optimal extractors one can build a
$(1-\epsilon,O({1 \over \epsilon}))$ list decodable codes of rate
$\Omega({\epsilon \over {log{1 \over \epsilon}}})$ and alphabet
size ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint