Compression with Graphical Constraints: An Interactive Browser (LTHC)
In this work we consider the problem of searching in a database of objects with different popularity. Contrary to traditional databases, users do not submit queries that are subsequently matched to objects. Instead, a search for a target object is conducted in several phases. In each phase, a user is presented with a list of database objects. The user selects from this list the object that is most similar to the target she wishes to find. A new list is then presented to the user, and the above process is repeated. When the target item is among the items presented to the user, she retrieves this item and the search terminates…
Wireless Keyboard & Mouse/Trackpad App for iOS (LCM)
The goal of this project is to develop an iOS app (for iPad/iPhone) which acts as a remote keyboard and track-pad for a laptop. For connecting to the laptop, the app can use either Bluetooth or WiFi. The app should use the default touch keyboard of an iPad/iPhone and add to this keyboard custom features as needed. Custom features can include for example gestures, special keys (CTRL, Command, Shift), interactions with the mouse, etc…
Correlation Decay for LDPC Codes (LTHC)
Low Density Parity Check Codes nowadays form a basic paradigm of error correcting codes on graphs. The underlying graphical structure induces a distance between two bits in a codeword. An important question concerns the behavior of the correlation (or covariance) between pairs of bits as a function of the graph distance. An answer to this problem would have applications in a number of other situations…
Error Exponents and Statistical Mechanics (LTHC)
There are various performance measures for a code. An important one is given by the error exponents, which give the exponential speed of decay of the error probability for transmission rates below the channel capacity. These exponents are known for Shannon’s random code ensemble but beyond that, there still remains many open questions, specially at low rate…
Community Detection in Directed Graphs (LTHI)
The problem of clustering or “community detection” in large random graphs has received a lot of attention recently. One thoroughly studied model is the so called “stochastic block model” (SBM), which models random indirect graphs with multiple communities. In the present project, we aim at studying the community detection problem in directed random graphs. Interesting questions arise from the fact that the graph is directed…
Analyzing the Structure of Wikipedia (LTHI)
The aim of this project is to analize the structure of a large existing web graph such as Wikipedia with roughly $N = 6$ million nodes and $E = 200$ million edges. Spectral algorithms exist for such tasks, but their run time $O(N^3)$ is prohibitive for the above application. Various methods have been developed for tackling this issue. We aim at studying and implementing some of these…