^May June – 2011 ^July

In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to transmit n bits to n receivers (one bit to each), where the receivers reside at the nodes of a graph G and have prior access to the bits corresponding to their neighbors in the graph (side information). The objective is to find a code word of minimum length which will allow each receiver to learn their own bit given access to the code word and their side information. When the encoding is linear (this is known as linear index coding), the minimum possible code word length corresponds to a graph parameter known as the minrank of G. In this talk, we will describe an algorithm which approximates the minrank of a graph in the following sense: when the minrank of the graph is a constant k, the algorithm finds a linear index code of length O(n^(f(k))). For example, for k=3 we have f(3) ~ 0.2574. This algorithm exploits a connection between minrank and a semidefinite programming (SDP) relaxation for graph coloring introduced by Karger, Motwani and Sudan. A result which arises from our analysis, and which may be of independent interest, gives an exact expression for the maximum possible value of the Lovasz theta-function of a graph, as a function of its minrank. This compares two classical upper bounds on the Shannon capacity of a graph. Based on joint work with Ishay Haviv.

In recent years, we have used software engineering tools to develop reactive models to simulate and analyze the development of organs. The modeled systems embody highly complex and dynamic processes, by which a set of precursor stem cells proliferate, differentiate and move, to form a functioning tissue. Three organs from diverse evolutionary organisms have been thus modeled: the mouse pancreas, the C. elegans gonad, and partial rodent brain development. Analysis and execution of the models provided dynamic representation of the development, anticipated known experimental results and proposed novel testable predictions. In my talk, I will l discuss challenges, goals and achievement in this direction in science.

Throughout the past decade there has been extensive research on algorithmic and data mining techniques for solving the problem of influence maximization in social networks: if one can convince a subset of individuals to influence their friends to adopt a new product or technology, which subset should be selected so that the spread of influence in the social network is maximized? Despite the progress in modeling and techniques, the incomplete information aspect of problem has been largely overlooked. While the network structure is often available, the inherent cost individuals have for influencing friends is difficult to extract. In this talk we will discuss mechanisms that extract individuals' costs in well studied models of social network influence. We follow the mechanism design framework which advocates for truthful mechanisms that use allocation and payment schemes that incentivize individuals to report their true information. Beyond their provable theoretical guarantees, the mechanisms work well in practice. To show this we will use results from experiments performed on the mechanical turk platform and social network data that provide experimental evidence of the mechanisms' effectiveness.