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 Abstract: 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 <http://www.wisdom.weizmann.ac.il/images/GPS-ShamgarGurevich.pdf)> --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Yaeli Malka <yaeli.malka@weizmann.ac.il>