This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:projects:details:mah01 [2009/04/07 15:28] admin created |
en:projects:details:mah01 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | === Private Information Retrieval and Locally Decodable Codes === | ||
| - | |||
| - | |||
| - | 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 : Private Information Retrieval and Locally Decodable Codes | title : Private Information Retrieval and Locally Decodable Codes | ||
| Line 17: | Line 6: | ||
| contactroom: BC 148 | contactroom: BC 148 | ||
| type : master semester, master thesis | type : master semester, master thesis | ||
| - | status : available | + | state : unavailable |
| table : projects | table : projects | ||
| created_dt : 2009-01-01 | created_dt : 2009-01-01 | ||
| Line 27: | Line 16: | ||
| template:datatemplates:project | template:datatemplates:project | ||
| ---- | ---- | ||
| + | |||
| + | 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. | ||