Events Type: Computer Science seminar
June 28, Tuesday
12:00 – 13:00
Linear Index Coding via Semidefinite Programming
Computer Science seminar
Lecturer : Eden Chlamtac
Affiliation : Computer Science Department,
Location : 202/37
Host : Dr. Aryeh Kontorovich
show full content
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.
June 14, Tuesday
12:00 – 13:00
Modeling Organogenesis: Scaling Development from Stem Cells to Organs
Computer Science seminar
Lecturer : Yaki Setty
Affiliation : Faculty of Mathematics and Computer Science,The Weizmann Institute of Science
Location : 201/37
Host : Dr. Gera Weiss
show full content
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.
June 1, Wednesday
12:00 – 13:00
How to win Friends and Influence People, Truthfully
Computer Science seminar
Lecturer : Yaron Singer
Affiliation : Computer Science Division, UC Berkeley
Location : 202/37
Host : Dr. Aryeh Kontorovich
show full content
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.