The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
                 Mathematical Analysis and Applications Seminar
                     Lecture Hall, Room 1, Ziskind Building
                         on Tuesday, December 18, 2012
                                  11:00 - noon
                                Shamgar Gurevich
                       University of Wisconsin - Madison
                                 will speak on
              Solving the GPS Problem in Almost Linear Complexity
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.
(See more details in
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <> 
Announcement from: Yaeli Malka   <>