^November December – 2011 ^January

Multi-level marketing is a marketing approach that motivates its participants to promote a certain product among their friends. The popularity of this approach increases due to the accessibility of modern social networks, however, it existed in one form or the other long before the Internet age began (the infamous Pyramid scheme that dates back at least a century is in fact a special case of multi-level marketing). In this talk we lay foundations for the study of reward mechanisms in multi-level marketing within social networks. We provide a set of desired properties for such mechanisms and show that they are uniquely satisfied by geometric reward mechanisms. The resilience of mechanisms to false-name manipulations is also considered; while geometric reward mechanisms fail against such manipulations, we exhibit other mechanisms which are false-name-proof. The talk will be self-contained.

The age of the internet and the pervasiveness of networked computing enabled the creation of large computational systems in which multiple autonomous entities interact. The designers of such systems face difficult challenges: they must bring about the desired behavior of the system as a whole while accounting for the disjoint behavior and incentives of individual agents. I will present a few examples of research (with various collaborators) that deals with these challenges in the context of different systems. I will discuss recent work on incentives for information dissemination in the Bitcoin protocol (a distributed electronic currency that has received much attention recently) and in social networks, as well as work on the interactions within closed P2P communities, and on core network protocols such as TCP and BGP.

A typical learning process begins with some prior beliefs about the target concept. These beliefs are refined using evidence, typically a sample. The evidence is used to compute a “posterior belief”, which assigns a probability distribution over the hypotheses class. The Bayes optimal hypothesis is the average hypothesis, weighted by the posterior. However, this hypothesis is often prohibitively costly to compute. Therefore, there is a need for an algorithm to construct a hypothesis (either a single hypothesis or some combination), given the posterior belief. Several methods have been proposed for this problem: for example, Gibbs sampling, ensemble methods, and choosing the maximum posterior. We propose a new method: choosing the median hypothesis. This method is close to the average Gibbs classifier and Bayes optimal classifier in terms of accuracy while having the same run-time efficiency, during the generalization phase, as the maximum posterior method. In this talk, we will define a measure of depth for hypotheses, from which we derive the median hypothesis. We present generalization bounds which leverage the PAC-Bayes analysis technique. We present an algorithm to approximate the median hypotheses and we prove its correctness. Our definition of median is closely related to Tukey's median; in fact our algorithm provides a polynomial approximation to the problem of finding the Tukey median. This is a joint work with Chris J. C. Burges

We will introduce a “learning” multi-scale iterative process for data analysis. This process approximates a task related function that is defined on a given data-set by using the geometric structures of the data in different scales. The constructed multi-scale representation can be easily extended to new data points. We will provide a number of examples including classification and regression, extension of non-linear embedding coordinates, and forecasting time series.

Linear programming (LP) and semidefinite programming (SDP) are powerful convex optimization tools which have become ubiquitous in the field of approximation algorithms in the last few decades. Given a combinatorial optimization problem (e.g. Maximum Independent Set), a standard approach to obtain an approximation algorithm is as follows: formulate the problem as an integer program (IP), relax this formulation to an LP or SDP, solve the relaxation, and then "round" the solution back to an integer solution. This approach is limited by how well the convex program (LP or SDP) approximates the original IP formulation, i.e. the integrality gap. One way to circumvent this limitation is through hierarchies of convex programs, which give a systematic way of iteratively strengthening any relaxation (at the cost of increased running time to solve it), so that the integrality gap gradually decreases. While initially, most of the literature on hierarchies in the context of approximation algorithms had focused on impossibility results,there has been a surprising surge of recent positive results. I will survey this recent development, by describing a number of combinatorial optimization problems for which we have been able to achieve improved approximations using hierarchies.

Two key synchronization paradigms for the construction of scalable concurrent data-structures are software combining and elimination.Elimination-based concurrent data-structures allow operations with reverse semantics (such as push and pop stack operations) to "collide" and exchange values without having to access a central location. Software combining, on the other hand, is effective when colliding operations have identical semantics: when a pair of threads performing operations with identical semantics collide, the task of performing the combined set of operations is delegated to one of the threads and the other thread waits for its operation(s) to be performed. Applying this mechanism iteratively can reduce memory contention and increase throughput. We present DECS, a novel Dynamic Elimination-Combining Stack algorithm,that scales well for all workload types. While maintaining the simplicity and low-overhead of an elimination-based stack, DECS manages to benefit from collisions of both identical- and reverse-semantics operations. Our empirical evaluation shows that DECS scales significantly better than both blocking and non-blocking best prior stack algorithms. This is joint work with Gal Bar-Nissan and Danny Hendler.

In the past decade the importance of natural language text processing (NLP) has grown immensely. The first steps in NLP applications involve identification of topics, entities, concepts, and relations in text. Traditionally, statistical models have been successfully deployed for the aforementioned problems. However, the major trend so far has been:"scaling up by dumbing down"- that is, applying sophisticated statistical algorithms operating on very simple or low-level features of the text. In this talk I will be making an argument that it is essential to use knowledge in NLP, propose several ways of doing it, and provide case studies on several fundamental NLP problems. The first problem I will address is entifying "important" expressions in input text and cross-linking them to Wikipedia pages describing these expressions.This approach allows to enrich the input text with knowledge from Wikipedia. Then, I'll describe an approach for utilizing knowledge imported from Wikipedia for co-reference resolution, the task of understanding that in the expression "Obama addressed the nation, I need your help, he said", ""he" refers to Obama and "your" refers to the American nation.

Database transformations (queries, views, mappings) take apart, filter,and recombine source data in order to populate warehouses, materialize views,and provide inputs to analysis tools. As they do so, applications often need to track the relationship between parts and pieces of the sources and parts and pieces of the transformations' output. This relationship is what we call database provenance. This talk presents an approach to database provenance that relies on two observations. First, provenance is a kind of annotation, and we can develop a general approach to annotation propagation that also covers other applications, for example to uncertainty and access control.In fact, provenance turns out to be the most general kind of such annotation,in a precise and practically useful sense. Second, the propagation of annotation through a broad class of transformations relies on just two operations: one when annotations are jointly used and one when they are used alternatively.This leads to annotations forming a specific algebraic structure, a commutative semiring.The semiring approach works for annotating tuples, field values and attributes in standard relations, in nested relations (complex values), and for annotating nodes in (unordered) XML. It works for transformations expressed in the positive fragmentof relational algebra, nested relational calculus, unordered XQuery, as well as for Datalog, GLAV schema mappings, and tgd constraints. Finally, when properly extended to semimodules it works for queries with aggregates. Specific semirings correspond to earlier approaches to provenance, while others correspond to forms of uncertainty, trust, cost, and access control. This is joint work with Y. Amsterdamer, D. Deutch, J.N. Foster, T.J. Green,Z. Ives, and G. Karvounarakis, done in part within the frameworks of the Orchestra and pPOD projects.