Solving the GPS Problem in Almost Linear Time

-
Shamgar Gurevich, University of Wisconsin-Madison
Fine Hall 214

A client on the earth surface wants to know her geographical location. The Global Positioning System (GPS) was built to fulfill this task. It works as follows. Satellites send to earth their location. For simplicity, the location of a satellite is a bit b=1,-1. The satellite transmits to the earth a sequence of N>1000 complex numbers S[0],S[1],...,S[N-1] multiplied by its location b. The client receives the sequence R which is a noisy version of S distorted in two parameters that encode the distance and relative radial velocity of the satellite with respect to the client. The GPS PROBLEM is to calculate the distance and the bit b. A client can compute her location by knowing the locations of at least three satellites and distances to them. The current sequences S which are used are pseudo-random and the algorithm takes O(N^2 logN) arithmetic operations. In this lecture I will explain our recent construction of sequences S that allow a much faster algorithm: it solves the GPS Problem in O(N logN) operations. This is a joint work with A. Fish (Sydney), R. Hadani (Austin), A. Sayeed (Madison), and O. Schwartz (Berkeley).