Speaker

Johannes Blömer

Title

Sums of Square Roots, Travelling Salesmen and Diophantine Approximation

Abstract

In geometric problems where the inputs are points in Euclidean space — for example, the Euclidean travelling salesman problem — comparing the quality of different solutions comes down to determining the sign of a sum of square roots. However, it is not known how to do this in polynomial time since the best-known lower bounds for the distance of a sum of square roots to zero are doubly exponential in the number of summands. Consequently, it is not known whether the Euclidean travelling salesman problem (ETSP) is in NP. This talk will discuss the current state of research on the sums of square roots problem. In particular, we will discuss the close connection between the sums of square roots problem and quantitative versions of the celebrated Thue–Siegel–Roth theorem and the subspace theorem from diophantine approximation. The talk is partially based on joint work with Friedrich Eisenbrand.

Bio

Since 2000 Prof. Dr. Johannes Blömer is a professor in the Department of Computer Science of Paderborn University, where he leads the Codes and Cryptography group. He has done work in various areas of theoretical computer science, including complexity theory, clustering, algorithmic number theory and, (post-quantum) cryptography and security. His work in cryptography ranges from number theoretic foundations, e.g. in lattice theory, to the construction and formal analysis of cryptographic primitives and to practical aspects, e.g. side-channel attacks and secure implementations. His work has been published in leading conferences and journals of computer sciences and cryptography like CRYPTO, Eurocrypt, ACM CCS, ICALP, FOCS, and STOC. He served on various program committees and is on the board of two journals in theoretical computer science.

Language

English (Offline)