Andrea Montanari

Large matrices beyond singular value decomposition: A number of data sets are naturally described in matrix form. Examples range from microarrays to collaborative filtering data. In many of these examples, singular value decomposition (SVD) provides an efficient way to construct a low-rank approximation thus achievieng a large dimensionality reduction. SVD is also an important tool in the design of approximate linear algebra algorithms for massive data sets. It is a recent discovery that --for `generic' matrices-- SVD is sub-optimal, and can be significantly improved upon. There has been considerable progress on this topic over the last year, partly spurred by interest in the Netflic challenge. I will overview this progress.

Yun Song

Combinatorial stochastic processes in mathematical population genetics: Random combinatorial structures arise naturally in mathematical population genetics. For example, under certain population genetics models, the probability of observing a sample of DNA sequences is closely related to the distribution of exchangeable random partitions. This so-called sampling probability has a number of important applications in population genetics, but unfortunately closed-form formulas are rarely known. Because obtaining exact analytic results is a formidable problem, recent research has focused on developing sophisticated and computationally-intensive Monte Carlo techniques, such as MCMC or importance sampling. In this talk, I will review the aforementioned connection between combinatorial stochastic processes and population genetics, and describe a technique based on asymptotic analysis for obtaining novel closed-form sampling formulas.

Shaddin Dughmi

Randomization in Algorithmic Mechanism Design: Algorithmic mechanism design is concerned with problems where the inputs are a-priori unknown to the algorithm designer, and must be elicited from self-interested agents. Designing algorithms for resource allocation problems that achieve a good approximation ratio in polynomial time, despite the selfish behavior of agents holding the inputs, is a central research direction at the intersection of computer science and economics. Until recently, most of the known positive and negative results pertain to deterministic mechanisms. In particular, recent results have indicated that the power of deterministic truthful mechanisms can be severely bounded. However, we have recently shown that employing randomization may bridge the gap between truthful mechanisms and algorithms with full access to the inputs. I will discuss recent results on the power and limitations of randomization in algorithmic mechanism design, using examples such as multi-unit and combinatorial auctions.

Jan Vondrak

Randomized rounding in the matroid polytope: The question how to round a fractional solution in a matroid polytope has emerged recently in various settings, ranging from the submodular welfare maximization and submodular maximization with linear constraints, to problems like congestion minimization in network routing, the degree-constrained spanning tree and the asymmetric traveling salesman problem. In all these applications, it is useful to have a randomized rounding procedure which preserves the marginal probabilities on the elements and satisfies strong concentration bounds for certain functions of the rounded solution. Various approaches have been proposed in different settings, e.g. the dependent rounding of Gandhi et al. for bipartite matchings, pipage rounding of Calinescu et al. for matroids, and maximum entropy sampling of Asadpour et al. for spanning trees. I will describe a simple rounding procedure which has the above properties for any matroid and satisfies Chernoff-type concentration bounds for linear functions as well as monotone submodular functions. I will illustrate the usefulness of this technique on various examples. Joint work with Chandra Chekuri (UI Urbana-Champaign) and Rico Zenklusen (ETH Zurich).

Grant Schoenebeck

Unconditional hardness results for semi-definite programs: Integrality gaps for the Lasserre hierarchy: Semidefinite programs provide the best approximation algorithms for many NP-hard combinatorial optimization problems. Recently, techniques were developed to give unconditional lower bounds for algorithms based on SDPs. I will define and give background about semidefinite programming (and linear programming) hierarchies, which include a large class of SDPs (and LPs) including all the most famous SDP algorithms (which actually occur very low in the hierarchy). I will then show a lower bound that implies no SDP in this large class can refute a random 3-XOR instance (even though such an instance is very far from satisfiable). Finally, I will discuss some corollaries, implications, and open problems. This result is the first construction of a Lasserre integrality gap, and simplifies, strengthens, and helps to explain several previous results.

Parikshit Gopalan

List-decoding using deletions: A list-decoder for an error-correcting code is an algorithm that recovers a list of all codewords within a given radius of any received word. In designing list-decoders, one has to ask: what is the larg= est radius up to which the list is guaranteed to be small? A "black-box" approach to this problem is to apply the classical Johnson bound, which guarantees a small list up to the Johnson radius. This radius only depends on the minimum distance and is oblivious to all other information about the code. Thus for many natural codes, one could hope to do better. We present a "white-box" approach which for some codes allows decoding well beyond the Johnson radius. We identify a few "bad" codewords = and then "delete" them from the code, thereby improving the minimum distance and now invoke the Jo= hnson bound. We will apply this template to decoding linear transformations= , tensor-product codes and low-degree polynomials. This talk covers joint work with Venkatesan Guruswami, Adam Klivans, Prasad Raghavendra and David Zuckerman.