```
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>
----------
```