Miklos Ajtai

The role of lattices in complexity theory and cryptography: There are many ways of generating lattices at random. For some of these randomizations there are equivalences between average-case and worst-case algorithmic problems. Such an equivalence can be used for cryptographic purposes. The reason why such an equivalence exists for lattices is the symmetricity (that is, invariance under linear transformations) inherent in the set of all lattices and in the distribution that we use for picking a random lattice. This distribution sometimes only approximates a symmetric one so it may not be apparent. There is another symmetry in the possible ways of the representations of a lattice by different bases. These symmetries imply the nice properties of lattices which make average-case worst-case equivalences possible.

Shuchi Chawla

Approximation Algorithms for Planning Problems: Given a weighted undirected graph with "rewards" on nodes, the Orienteering problem involves finding a path of length at most D in the graph between two given nodes that covers the maximum possible reward. Such "path-planning" problems involving timing constraints arise in a variety of applications, for example, transportation and delivery problems, supply chain management, and robot navigation. We consider a variety of path-planning problems with timing constraints, and review some recent results on approximating these problems. We also consider planning problems on probabilistic graphs (Markov decision processes), and present some preliminary results for them.

Michael Luby

Application-layer FEC codes for mobile wireless broadcast and multicast services: Abstract TBA.

Constantinos Daskalakis

The Complexity of Nash Equilibria: In 1951, Nash showed that every game has a mixed Nash equilibrium. His proof is a reduction to Brouwer's fixpoint theorem and places the problem of finding equilibria into the realm of 'exponential existence proofs'. In fact, whether Nash equilibria can be computed in polynomial time has remained open since that time, and has come under increased scrutiny during the past two decades. In this talk, I will present some recent results (joint work with Paul Goldberg and Christos Papadimitriou) that shed light to this problem, in the negative direction.

Jason Hartline

Mechanism Design via Machine Learning: We consider the problem of designing nearly optimal mechanisms without prior knowledge of the distribution from which agent's valuations are drawn. In this setting, we use techniques from sample-complexity in machine learning to reduce problems in optimal mechanism design to those in classical (non-game theoretic) optimization. Our reductions imply that for these problems, given an optimal algorithm for the classical optimization problem, we can convert it into a $(1+\epsilon)$-approximation for the incentive-compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the comparison class of solutions. We apply these results to the problem of auctioning a digital good, the attribute auction problem, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a machine learning perspective, these settings present several challenges: in particular, the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large. This is joint work with Maria-Florina Balcan, Avrim Blum, and Yishay Mansour.

Vladlen Koltun

The Arrangement Method for Linear Programming: We present a new combinatorial method for linear programming. Like the simplex method, it takes a walk on a graph. However, the graph it walks on has considerably better structure than polytope graphs, including a small polynomial diameter. Among other things, this implies that the status of the Hirsch conjecture can no longer be viewed as a fundamental stumbling block on the road to a strongly polynomial algorithm for linear programming.

Satish Rao

Recent progress on Sparsest Cuts and Metric Embeddings: We present ideas from recent results on embedding $\ell_2^2$ metrics into $\ell_2$ metrics. In particular, we will present the proof of Arora, Lee and Naor that shows that this is possible with distortion at most $O^*(\sqrt{\log n})$ (ignoring $\log \log n$ factors.) We start with building blocks from Arora, Rao, and Vazirani, and Chawla, Raecke, and Gupta. These results have application in approximation algorithms and have application in functional analysis.