Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
en:projects:details:fred02 [2009/04/07 15:21]
admin created
en:projects:details:fred02 [2010/01/20 13:08]
masoud
Line 1: Line 1:
-=== Shortest paths in a Euclidean graph === 
- 
- 
-In the "​Private Information Retrieval (PIR)" problem, a database is shared between several servers. The goal is to query the database for a particular piece of information without giving any of the servers a clue on what information we are actually interested in. If there was only one server, the only solution would be to acquire the whole database and then keep the relevant information. But it turns out that with more than one server (that do not communicate with each other), one can do much better. ​ 
- 
-This problem is closely related to a fundamental problem in theoretical computer science and coding theory, namely, Locally Decodable Codes (LDC). An LDC is an error correcting code with the property that, given a possibly corrupted encoded message, one can decode any particular bit of the sent message (with high confidence) by reading the received sequence only at a small number of (random) coordinates. ​ 
- 
-The aim of this project is to study and understand the major results on the two aforementioned problems and their connections. The project is suitable for Masters students with a theoretical interest. It may or may not involve computer programming,​ depending on the student'​s preference. 
- 
---- 
- 
 ---- dataentry project ---- ---- dataentry project ----
 title : Shortest paths in a Euclidean graph title : Shortest paths in a Euclidean graph
-contactname: ​Frederic Didier +contactname: ​Harm Cronie 
-contactmail_mail: ​frederic.didier@epfl.ch +contactmail_mail: ​harm.cronie@epfl.ch 
-contacttel: 021 6931204 +contacttel: 021 6936793 
-contactroom:​ BC 128+contactroom:​ BC 150
 type : bachelor semester type : bachelor semester
-status : available+status : completed
 table : projects table : projects
 created_dt : 2009-01-01 created_dt : 2009-01-01
-taken_dt :  +taken_dt : 2009-06-15 
-completed_dt : +completed_dt : 2010-01-13 
-by : +by : Auguste Carmen Lunang Pomkam
 output_media : output_media :
 ====== ======
 template:​datatemplates:​project template:​datatemplates:​project
 ---- ----
 +
 +Finding the shortest path between two vertices in a weighted graph is a fundamental problem with numerous applications. There are of course classical algorithms for this problem like Dijkstra'​s Algorithm, but in many applications this algorithm is too slow, for example when we want to compute the best path between two cities in the graph of the roads of a whole country.
 +
 +For this kind of problem, it is crucial to use the Euclidean property of the graph to design better algorithms. A classical approach is to use the A* search which uses an estimation on the minimal distance to minimize the search space in Dijkstra'​s algorithm. But if one is allowed to do some precomputations on the graph and to store some extra data, it is possible to answer any shortest path query between two points very efficiently.
 +
 +The aim of the project is to understand and implements some of these algorithms. ​