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 , which generalises to give an O(\log^{ k-1\lceil k/3\rceil } n) query algorithm for the k-dimensional problem when k 3.