Differences

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

--- en:projects:mth:masterlthcamin1 [2010/11/24 17:17]
karbasi
+++ en:projects:mth:masterlthcamin1 [2012/12/20 09:26] (current)
behn
@@ Line 1: / Line 1: @@
-**A New Model for an Interactive Browser**
+//Doctoral School or Master thesis project//\\
+\\
+=====Compression with Graphical Constraints: An Interactive Browser=====
 In this work we consider the problem of searching in a
-database of objects with difference popularities. Contrary to traditional
+database of objects with different popularities. Contrary to traditional
 databases, users do not submit queries that are subsequently
 matched to objects. Instead, a search for a target
@@ Line 30: / Line 35: @@
 over large datasets prohibitive.
-One way to address the above constraints is through a graphical model, i.e., each group here must conform to the constraints
+One way to address the above constraints is through a graphical model, i.e., each query set  must conform to the constraints
-imposed by a graph . For instance, items (with potentially different popularity) can be associated with vertices and each pool is any set of
+imposed by a graph . For instance, items (with potentially different popularity) can be associated with vertices and each query is any set of
-nodes that must be path connected. In this context, as  a special case the optimum algorithm for finding an object on a complete graph reduces to that of Huffman coding.
+nodes that is path connected. In this context, as  a special case the optimum algorithm for finding an object on a complete graph reduces to that of Huffman coding.
+**Goals**\\
+Intuitively, the efficiency of an algorithm that can find a target by using the membership oracle with graphical constraints should depend on the entropy of the objects as well as the charactersitics of the graph. We would like to understand this depencency.
+**Prerequisites:**\\
+Programming skills and basic notions of information theory
+**Supervisor:**\\
+Amin Karbasi, amin.karbasi@epfl.ch\\
+**Professor:**\\
+Ruediger Urbanke, office INR 116 ruediger.urbanke@epfl.ch
 [[en:projects:masterthesis:mtp|back to master projects menu]]