2012-2013 Seminars

We study algorithms for combinatorial market design problems, where a collection of objects are priced and sold to potential buyers subject to equilibrium constraints. We introduce the notion of a combinatorial Walrasian equilibrium (CWE) as a...

One of the major insights of the ``fixed-parameter tractability’’ (FPT) approach to algorithm design is that, for many NP-hard problems, it is possible to efficiently *shrink* instances which have some underlying simplicity. This preprocessing can...

We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers...

A twenty-year old conjecture by Manickam, Mikl\'os, and Singhi asked whether for any integers $n, k$ satisfying $n \ge 4k$, every set of $n$ real numbers with nonnegative sum always has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is...

A matrix A naturally defines a quadratic form x^tAy. If A is of rank <=r, then the rank<=r decomposition of A corresponds naturally to a size ~2nr circuit for computing the quadratic form. It is clear how to perform "white box" polynomial identity testing for such circuits, and the motivating question for this work is to explore black-box identity testing. The probabilistic method shows that there is a size ~2nr hitting set for such polynomials. In this work we match this bound (over large fields), which is optimal up to constant factors. Further, we explore how A can be reconstructed from the evaluations of the quadratic form. Similar probabilistic constructions show that there exist ~4nr evaluations which determine any such matrix A. Again, we match this bound (over large fields) with an explicit construction, and furthermore give a polynomial-time algorithm to reconstruct A from such evaluations. More generally, we show an efficient reduction from (exact) low-rank matrix reconstruction to (exact) sparse recovery. This reduction is novel in the compressed-sensing realm as it is field independent and unrelated to convex optimization. Finally, using matrices as a base case we also derive a quasi-polynomial hitting set for higher-order tensors. Joint work with Michael Forbes.

Shor's algorithm, the hallmark quantum algorithmic breakthrough, has been successfully generalized to address a variety of related algebraic problems. Generalizations to nonabelian settings could have striking consequences, but such efforts have...

If $x$, $y$, and $z$ are random vectors, what is the expectation of the product of their inner products, $\langle x,y \rangle$, $\langle y, z \rangle$, $\langle z, x\rangle$? If $U$ and $V$ are random unitary matrices, what is the expected trace of...