אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Gurus are individuals who claim to possess mental powers of insight and prediction that far surpass those of the average person; they compete over followers, offering them insight in return for continued devotion. Followers wish to harness a (true) Guru’s predictive power but (i) have limited attention span and (ii) doubt the Guru’s predictive advantage over them. This dynamic raises the question of follower retention: how do Gurus retain the faith of their flock in the face of limited attention and competition? This problem is not merely a spiritual one but one that also affects automated interactive processes competing for limited user attention in today’s congested Information World.

The phenomenon that a Guru wishes to instruct her followers about is modeled here by a distribution over a sequence of (possibly correlated) events. We define a natural class of retentive scoring rules to model the way followers evaluate Gurus they interact with. We show that these rules are tightly connected to the classical notion of truth-eliciting “proper scoring rules” studied in Decision Theory since the 1950’s [McCarthy, PNAS 1956].

Next, we move our attention from the dynamics of interaction between Guru and follower to the study of the intrinsic properties of distributions that deem them appropriate for instruction by a Guru. More to the point, we define the retention complexity of a distribution as the minimal initial level of “faith” that a follower should have before approaching the Guru, in order for the Guru to retain that follower throughout the full collaborative discovery process.

Finally, we initiate the study of the retention complexity of linear spaces over finite fields. We show (i) the retention complexity of Walsh-Hadamard codes is constant and (ii) that of random Low Density Parity Check (LDPC) codes is, with high probability, linear in the code’s blocklength; intriguingly, for these two interesting families of codes, retention complexity is roughly equal to query complexity as locally testable codes.