| Title | : | The sum of square-roots problem |
| Speaker | : | Nikhil Balaji (IIT Madras) |
| Details | : | Mon, Jul 13, 2026 3:00 PM, @ SSB 334 |
| Abstract | : | 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, dots, b_m, check if sqrt{a_1} + sqrt{a_2} + dots + sqrt{a_n} > sqrt{b_1} + sqrt{b_2} + dots + sqrt{b_m}. The problem has a trivial linear time algorithm on the real RAM (just compute the sums and compare them!) 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. I will survey what is known about this problem and the difficulty in obtaining an efficient algorithm. I will present an interesting observation that gives an "efficient algorithm" for certain special cases of the problem and explain what it would take to make "efficient" actually efficient for the general case. Based on joint work with Samir Datta. Speaker bio: Nikhil is an assistant professor in the Department of Computer Science and Engineering at IIT Delhi. His research lies in theoretical computer science, with a particular focus on complexity theory, automata theory and algebraic computation. Much of his recent work and interests have focused on decision problems in the theory of real and complex numbers and their applications to verification. More broadly, he is interested in understanding the boundary between efficient computation and computational hardness through algebraic problems. Cross listed aRtCS talk as well. |