• Calendar

July 17, Tuesday
12:00 – 13:00

A client on the earth surface wants to know his/her geographical location. The Global Positioning System (GPS) was built to ful…ll this task. It works as follows: Satellites send to earth their location. For simplicity, the location of a satellite is a bit b 2 f1g: 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 of the form R[n] = b
0
e 2i N !0
n
S[n +  0] +W[n]; (1) where 0 2 C is the complex amplitude, with j0j  1; !0 2 ZN encodes the radial velocity of the satellite with respect to the client,  0 2 ZN encodes the distance between the satellite and the client, and W is a random white noise. The GPS Problem is: Problem 1 (GPS Problem) Design S, and an e¤ective method of extracting (b;  0) from S and R satisfying (1). A client can compute his/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 they support takes O(N2 logN) arithmetic operations: In my lecture I will explain our recent construction of sequences S that allow us to introduce a much faster algorithm called the "Flag Method". It solves the GPS Problem in O(N logN) operations. This is a joint work with A. Fish (Mathematics, Madison), R. Hadani (Math- ematics, Austin), A. Sayeed (Electrical and Computer Engineering, Madison), and O. Schwartz (Electrical Engineering and Computer Science, Berkeley).