We study the approximate-coloring(q,Q) problem: Given a graph G, decide whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional hardness for this problem for any constant 3\le q < Q. For q \ge 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness ... more >>>

We consider the approximate nearest neighbour search problem on the Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that uses polynomial storage and word size $d^{O(1)}$ requires a worst case query time of $\Omega(\log\log d/\log\log\log d)$. The approximation factor may be as loose as $2^{\log^{1-\eta}d}$ for any ... more >>>