We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... more >>>