A coloring of a graph is {\it convex} if it
induces a partition of the vertices into connected subgraphs.
Besides being an interesting property from a theoretical point of
view, tests for convexity have applications in various areas
involving large graphs. Our results concern the important subcase
of testing for ... more >>>

We show that the Closest Vector
Problem with Preprocessing over infty Norm
is NP-hard to approximate to within a factor of $(\log
n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their
reductions are based on norm embeddings. However, ... more >>>

Diagonalization is a powerful technique in recursion theory and in
computational complexity \cite{For00}. The limits of this technique are
not clear. On the one hand, many people argue that conflicting
relativizations mean a complexity question cannot be resolved using only
diagonalization. On the other hand, it is not clear that ... more >>>