Hebrew University Amitsur Algebra Seminar ---------------------------------- Time: Thursday, December 20, 12:00-13:15 Place: math 209, HUJI Speaker: Shamgar Gurevich (University of Wisconsin - Madison) Title: Solving the GPS Problem in Almost Linear Complexity A "poster" for this talk, followed by a more detailed article can currently be accessed at: <http://www.math.technion.ac.il/~techm/temp/20121220GURE.pdf> 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. This is a joint work with A. Fish (Sydney), R. Hadani (Austin), A. Sayeed (Madison), and O. Schwartz (Berkeley). You are cordially invited! <http://math.huji.ac.il/amitsur.html> --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> To see today's activities and other future and past activities go to <http://www.math.technion.ac.il/~techm/today.html> Announcement from: Gili Schul <gili.schul@mail.huji.ac.il> ----------