In this paper we study a novel model in which agents arrive sequentially one after the other and each in turn chooses one action from a fixed set of actions to maximize his expected rewards given the information he possesses at the time of arrival. The information that becomes available affects the incentives of an agent to explore and generate new information. We characterize the optimal disclosure policy of a planner whose goal is to maximizes social welfare. The planner's optimal policy is characterized and shown to be intuitive and very simple to implement. As the number of agents increases the social welfare converges to the optimal welfare of the unconstrained mechanism. One interpretation for our result is the implementation of what is known as the 'Wisdom of the crowds'. This topic has become more relevant during the last decade with the rapid adaptation of the Internet. This is a joint work with Ilan Kremer and Motty Perry.

The goal of discriminative learning is to train a system to optimize a certain desired measure of performance. In simple classification we seek a function that assigns a binary label to a single object, and tries to minimize the error rate (correct or incorrect) on unseen data. In structured prediction we are interested in the prediction a structured label, where the input is a complex object. Typically, each structured prediction task has its own measure of performance, or task loss, such as word error rate in speech recognition, the BLEU score in machine translation or the intersection-over-union score in object segmentation. Not only that those task losses are much more involved than the binary error rate, the structured prediction itself spans an exponentially large label space. In the talk, I will present two algorithms each designed to the minimize a given task loss, and applied to speech recognition. In the first part of the talk, I will present an algorithm which aims at achieving a high area under the receiver operating characteristic (ROC) curve. This measure of performance is often used to evaluate the detection of events over time. We will give some theoretical bounds that relate the performance of the algorithm with the expected area under the ROC curve, and will demonstrate its efficiency to that task of keyword spotting, i.e., that detection of all occurrences of any given word in a speech signal. In the second part of the talk, I will describe a new algorithm which aims to minimize a regularized task loss. The algorithm is derived by directly minimizing a generalization bound for structured prediction, which gives an upper-bound on the expected task loss in terms of the empirical task loss. The resulting algorithm is iterative and easy to implement, and as far as we know, the only algorithm that can handle a non-separable task loss. We will present experimental results on the task of phoneme recognition, and will show that the algorithm achieves the lowest phoneme error rate (normalized edit distance) compared to other discriminative and generative models with the same expressive power.

Detection of edges in images is a fundamental task in low level image processing. Edges are important as they mark the locations of discontinuities in depth, surface orientation, or reflectance. Their detection can facilitate a variety of tasks including image segmentation and object recognition, with many applications ranging from medical to security. In this talk we focus on accurate detection of faint, low-contrast edges in very noisy images. This challenging problem raises some fundamental statistical and computational questions, for which we shall provide some (partial) answers: What are detection limits and how do these depend on the complexity of the assumed edges ? What are computationally efficient methods to detect various families of edges ? and finally, how well can one detect edges under severe computational constraints - namely with sub-linear complexity in the number of image pixels. Joint work with Inbal Horev, Sharon Alpert, Meirav Galun, Ronen Basri (WIS) and with Ery Arias-Castro (UCSD).

Workflow Satisfiability Problem (WSP) is defined as follows. We are given sets $S

{s_1,ldots ,s_k}$ of steps and $U

{u_1,ldots ,u_n}$ of users. For every step $s_i$ we have a list $L(s_i)$ users that are allowed to do it. There are relations $rho_jsubseteq Utimes U$ and some constraints of the form $(rho_j, S', S'')$ where $S',S''subseteq S$.

We are to decide whether there is a function $pi: S rightarrow U$ satisfying the following conditions:

* $pi(s_j)in L(s_j)$;

* Each constraint $(rho_j, S', S'')$ must be satisfied, i.e., there are $s'in S', s''in S''$ such that $(pi(s'),pi(s''))in rho_j$.

Let k-WSP be WSP with parameter k (k is often small in practice).

Wang and Li (2010) showed that (i) WSP is NP-complete, (ii) k-WSP is W[1]-hard (iii) WSP(

,neq) is fixed-parameter tractable. Here $

$ and $neq$ are relations ${(s,s): sin S}$ and ${(s,s'): sneq s'in S}$, respectively.

We 'significantly' improved the FPT-algorithms of Wang and Li and proved that our algorithms cannot be 'significantly' improved any further unless the Exponential Time Hypothesis fails, extended the set of relations, and investigated some cases when WSP has polynomial kernel or not (subject to a well-known complexity theory hypothesis). Our results also improve some results of Fellows et al. (2011) on a problem related to WSP(neq).

Joint work with Jason Crampton (Information Security Group, RHUL) and Anders Yeo (Singapore Univ. Design & Technology) accepted for publication at ACM Transactions on Information and System Security; preliminary version in ACM Conference on Computer and Communications Security 2012, 857-868.

Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. In the first part of the talk we will focus on the advice complexity of this kind of questions, in a probabilistic Turing machine model, and discuss how many bits of "help" we need to accept such languages. In the second part we will consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are $k$ fixed Boolean functions $f_1,dots,f_k$ and Alice and Bob have $k$ inputs $x_1,dots,x_k$ and $y_1,dots,y_k$, respectively. We consider In the {em eliminate} problem, Alice and Bob should output a vector $sigma_1,dots,sigma_k$ such that $f_i(x_i)neq sigma_i$ for at least one $i$ (i.e., their goal is to eliminate one of the $2^k$ output vectors); in {em choose}, Alice and Bob should return $(i,f_i(x_i,y_i))$ and in {em agree} they should return $f_i(x_i,y_i)$, for some $i$. The question, in each of the three cases, is whether one can do better than solving one instance.

Living organisms and intelligent agents are characterized by the flow of sensory information from a stochastic environment and the value of their decisions and actions. We first argue that the future value can be related, in Partially Observed Markov Decision Processes (POMDP), to the information needed for controlling the process. This leads to a simple relationship between sensory information, control information and reward rate, which completely characterizes metabolic information processing. Next, we argue that efficient planning and learning are related to the predictive information (mutual information between past and future) of the environment. We further argue that the sub-extensive nature of predictive information is responsible for the emergence of hierarchies and reverse hierarchies in planning and perception, the fundamental building blocks of cognition.

Proteins are the major building blocks of all living things; they mediate almost all biochemical reactions; and are the targets of almost all medicines. Proteins exert their biological function through unique three dimensional structures, encrypted in a linear genetic code. This linear coding of three dimensional structures is one of the hallmarks of life on earth. Deciphering the code would provide deep insights into fundamental questions in biology, and at the same time have major impact on medicine. This task, known as the protein structure prediction problem, has been a major challenge in computational biology over the last four decades. In my talk, I will give a brief introduction to the protein structure prediction problem and then present the way my group approaches it emphasizing software engineering and machine learning aspects. The talk is self-contained and does not require biological background.