Colloquium

Navigating the human genome is currently a 1-dimensional (1D) search: we can find a gene of interest by its coordinates on the linear sequence, along with its annotations and metadata. Graphs are typically used to represent gene associations, for example regulatory interactions, and a large body of research is devoted to reconstruct and analyse such networks in order infer unknown associations. However, 1D genome navigation and association networks typically lack the spatial context in which the underlying biological processes take place.

We consider distance queries in vertex labeled planar graphs. For any fixed $0 < \varepsilon \leq 1/2$ we show how to preprocess a planar graph with vertex labels and edge lengths into a data structure that answers queries of the following form. Given a vertex $u$ and a label $\lambda$ return a $(1+O(\varepsilon))$-approximation of the distance between $u$ and its closest vertex with label $\lambda$.

Big data analytics is a current title given to the process of analyzing large amounts of recorded information, for the purpose of discovering valuable insights from the data. It is widely used in the business world as well as in scientific research. The methodologies used for analysis combine statistical models or non-probabilistic models with iterative learning algorithms. The output would typically be a predictive rule that is based on information from many features, and can help anticipating an outcome for newly coming observations.

It is no secret that online companies, hospitals, credit-card companies and governments hold massive datasets composed of our personal and private details. Information from such datasets is often released using some privacy preserving heuristics, which have been repeatedly shown to fail. In contrast, differentially private algorithms release information about a given dataset while satisfying a powerful and mathematical guarantee of privacy.

Data is now collected and processed on tremendous scale. Unfortunately, in several crucial applications it is not possible to leverage the full extent of collected information, e.g. when attempting to identify global properties across sensitive data sets held by agent(s) who are unable or unwilling to share the information.

A common approach to statistical learning on big data is to randomly split it among m machines and calculate the parameter of interest by averaging their m individual estimates.

Focusing on empirical risk minimization, or equivalently M-estimation, we study the statistical error incurred by this strategy. We consider two asymptotic settings: one where the number of samples per machine $n\rightarrow\infty$ but the number of parameters $p$ is fixed, and a second high-dimensional regime where both $p,n\rightarrow\infty$ with $p/n\rightarrow\kappa$.

Macromolecular assemblies, cellular machines comprised of many individual proteins, perform many essential tasks in the cell. To understand how these assemblies function and to develop strategies to modulate them for therapeutic purposes, we need to describe the structure, dynamics and interactions of the underlying proteins. These large assemblies, however, often elude structural characterization by the conventional techniques of X-ray crystallography or NMR spectroscopy.

Graph matching is one of the most well-studied problems in combinatorial optimization, with applications ranging from scheduling and object recognition to numerical analysis and computational chemistry. Nevertheless, until recently very little was unknown about this problem in real-life {dynamic networks}, which aim to model the constantly changing physical world. 

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. For a collection of simultaneously transmitting stations, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly.

In multi-agent interactions, each agent often faces uncertainty over the incentives and the behavior of the other agents. The traditional approach assumes that agents each maximize their expected utility w.r.t. some common prior distribution. However in most real-world scenarios agents have no way to accurately or even approximately know this distribution. Moreover, numerous psychological experiments have demonstrated that human decision makers fail even at fairly simple tasks involving probabilistic reasoning, and are prone to cognitive biases such as risk-aversion and loss-aversion.

I will describe an alternative, non-probabilistic, model for representing players' uncertainty in games, inspired by artificial intelligence and bounded rationality approaches.

While the model is quite general, I will demonstrate how it applies for preference aggregation mechanisms (voting), overcoming many shortcomings of previous theories. My main result is that the behavior of bounded-rational agents boils down to a simple and natural dynamics, which is guaranteed to converge to an equilibrium. Extensive simulations show that the resulting equilibria replicate known phenomena from real-world voting.

Finally, I will show how key components of this approach can be extracted and applied to very different settings, including online scheduling on Doodle and routing in networks with uncertain congestion.

The talk is based on published and unpublished work with Omer Lev, David Parkes, Jeffrey S. Rosenschein, and James Zou.