The sum of square-roots problem

The sum of square-roots problem is an important computational problem in numerical analysis, with applications to computational geometry: Given positive integers a_1, a_2, ..., a_n and b_1, b_2, ..., b_m, check if √a_1 √a_2 ... √a_n > √b_1 √b_2 ... √b_m. The problem has a trivial linear time algorithm on the real RAM but surprisingly this is not a polynomial time algorithm in the traditional Turing machine model. This problem is an important subroutine in computational geometry (for example, Euclidean shortest path problem, Euclidean travelling salesperson problem), complicating the transfer of algorithms from the real RAM to the standard integer RAM.

The speaker will survey what is known about this problem, the difficulty in obtaining an efficient algorithm, and present an observation that gives an "efficient algorithm" for certain special cases. This is based on joint work with Samir Datta.