Before revision:  We show that these conjectures are false in dimension three or higher by giving an O(\log^2 n) query algorithm for the three-dimensional Tarski problem , which generalises to give an O(\log^{ k-1\lceil \rceil } n) query algorithm for the k-dimensional problem when k 3.
After revision:  We show that these conjectures are false in dimension three or higher by giving an O(\log^2 n) query algorithm for the three-dimensional Tarski problem . We also give a new decomposition theorem for k-dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an O(\log^{ k-1\lceil \rceil } n) query algorithm for the k-dimensional problem when k 3.