Seminars 2017

We study the problem of assigning a small subset of indivisible items to a group of agents so that the subset is agreeable to all agents, meaning that all agents value the subset as least as much as its complement. For an arbitrary number of agents and items, we derive a tight worst-case bound on the number of items that may need to be included in such a subset. We then present polynomial-time algorithms that find an agreeable subset whose size matches the worst-case bound when there are two or three agents. Furthermore, we investigate the problem of efficiently computing an agreeable subset whose size approximates the size of the smallest agreeable subset for any given instance. We consider three well-known models for representing the preferences of the agents---ordinal preferences on single items, the value oracle model, and additive utilities---and establish tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time in each of these models.

 

As the first decentralized cryptocurrency, Bitcoin has ignited much excitement, not only for its novel realization of a central bank-free financial instrument, but also as an alternative approach to classical distributed computing problems, such as reaching agreement distributedly in the presence of misbehaving parties, as well as to numerous other applications―contracts, reputation systems, name services, etc. The soundness and security of these applications, however, hinges on the thorough understanding of the fundamental properties of its underlying blockchain data structure, which parties (“miners”) maintain and try to extend by generating “proofs of work” (POW, aka “cryptographic puzzle”).

In this talk we formulate such fundamental properties of the blockchaincommon prefix, chain quality, chain growthand show how applications such as consensus and a robust public transaction ledger can be built ``on top'' of them, assuming the adversary’s hashing power (our analysis holds against arbitrary attacks) is strictly less than ½ and high network synchrony:

The above properties hold assuming that all parties―honest and adversarial―”wake up” and start computing at the same time, or, alternatively, that they compute on a common random string (the “genesis” block) only made available at the exact time when the protocol execution is to begin. In this talk we also consider the question of whether such a trusted setup/behavioral assumption is necessary, answering it in the negative by presenting a Bitcoin-like blockchain protocol that is provably secure without trusted setup, and, further, overcomes such lack in a scalable way―i.e., with running time independent of the number of parties [4].

A direct consequence of our construction above is that consensus can be solved directly by a blockchain protocol without trusted setup assuming an honest majority (in terms of computational power).

This talk addresses statistical inference with mixture and hierarchical models: efficiency of parameter estimation in finite mixtures, and scalable clustering of multilevel structured data. It is well-known that due to weak identifiability and singularity structures of latent variable models' parameter space, the convergence behaviors of parameter estimation procedures for mixture models remain poorly understood. In the first part of the talk, we describe a general framework for characterizing impacts of weak identifiability and singularity structures on the convergence behaviors of the maximum likelihood estimator in finite mixture models. This allows us to resolve several open questions regarding popular models such as Gaussian and Gamma mixtures, as well as to explicate the behaviors of complex models such as mixtures of skew normal distributions.

In the second part of the talk, we address a clustering problem with multilevel structured data, with the goal of simultaneously clustering a collection of data groups and partitioning the data in each group. By exploiting optimal transport distance as a natural metric for distributions and a collection of distributions, we propose an optimization formulation that allows to discover the multilevel clustering structures in grouped data in an efficient way. We illustrate the performance of our clustering method in a number of application domains, including computer vision .