Don Knuth

The talk is about a method for estimating Bell's number, which is the number of ways of partitioning n elements. We will be trying to understand how fast Bell's number grows, using the probabilistic method, taylor series, etc to get the bound. Knowledge of Complex theory key.

Jason Hartline, Microsoft Research

We consider the computational problem a monopolistic store owner faces when setting prices for the items for sale. Given the true combinatorial valuations of a set of consumers for the sale items, we look for pricings for the individual items such that

a) there is no squabbling between consumers (when they are all in the store at once). I.e, the pricing induces an envy-free allocation in which every consumer can obtain their utility maximizing allocation of items as if they were the only shopper in the store.

b) the seller's profit is optimized.

We consider the unit demand special case of this problem in which each consumer is assumed to want at most one item (e.g., sale of houses, or movies on airline flights). We review some pricing techniques from game-theory and use them to get a log-approximation. We show that a special case of this unit demand problem is APX-hard.

Finally, we consider the mechanism design problem of actually selling the items when the demands of the consumers are not publicly known in advance (and give a log approximation).

This is joint work with Anna Karlin and Claire Kenyon.

Sergei Vassilvitskii

While the number of undominated solutions to a multiobjective optimization problem may be exponential, the number of solutions that are approximately optimal is polynomial. We show a short proof of this fact, and describe algorithms (along with lower bounds) for computing the smallest such solution sets (also known as $\epsilon$-Pareto curves). Time permitting, we will present some of the many open problems in this area.

This is joint work with Mihalis Yannakakis.

Man-Cho Anthony So

One form of John's Theorem states that every convex body K contains an unique ellipsoid of maximal volume (and hence by duality, K is contained in an unique ellipsoid of minimal volume). Such ellipsoids are not just of pure mathematical interest. They are employed in, e.g. the ellipsoid method for linear programming. John's Theorem also gives a characterization of such ellipsoids. In this talk I will present a proof of this characterization using tools from functional analysis.

Mathieu Turuani

The verification of cryptographic protocols became of great importance with the developpement of communications and transactions on public channels, like internet. In this talk, I will present some complexity results for the protocol insecurity decision problem. These results use (and try to weaken) the hypothesis of cryptographic primitives reliability like the encryption. Indeed, many well known attacks rely only on specification weaknesses. Moreover, results introducing some properties of the cryptographic primitives will be presented, like algebraic properties and key commutation

Sriram Sankaranarayanan

Given a $n$-variable, degree-$m$ polynomial $p$, with real coefficients, we ask if $ p \geq 0$ over the reals. Such polynomials are called positive semi-definite (psd). An efficient solution to this problem is useful in the analysis of systems with non-linear dynamics. However, the problem is known to be NP-hard for m >=4.

A natural "relaxation" is to check if the polynomial in question can be expressed as a sum of squares of other polynomials. Such polynomials are called "sums of squares"(sos). In 1888, Hilbert showed that not every psd is a sos. Furthermore, he outlined *exactly* three instances (m=2, n=1, (m=4 and n=3)) where these two notions co-incide. A recent paper by P. Parrilo uses semi-definite programming to tackle this problem. Time permitting, I will show some more useful relaxations based on Groebner Bases.

Ho-Lin Chen

Self-assembly is the ubiquitous process by which objects autonomously assemble into complexes. Nature provides many examples: Atoms react to form molecules. Molecules react to form crystals and supramolecules. Cells sometimes coalesce to form organisms. It is widely believed that self- assembly will ultimately become an important technology, enabling the fabrication of great quantities of small complex objects such as computer circuits. DNA has emerged as an important component to use in self- assembly of nano-scale systems due to its small size, its incredible versatility, and the precedent set by the abundant use of DNA self- assembly in nature. Accordingly, DNA self-assembly has received significant attention over the last few years. I will talk about a thermodynamic model of DNA self-assembly and use it to analyze some of the error correction mechanisms.

Aaron Bradley

The static analysis community is familiar with abstract interpretation, a general framework introduced in P. Cousot's and R. Cousot's 1976 paper. Prior to this work, Michael Karr published his "Affine Relationships Among Variables of a Program" (1976). It "presents a practical approach to detecting [equality relationships that hold between a linear combination of the program variables and a constant] by considering the problem from the viewpoint of linear algebra." Besides being a beautifully written paper, it motivated the general framework of abstract interpretation. I will present the main results of the paper.

Damon Mosk-Aoyama

We consider a graph optimization problem that arises in the testing of systems. Our focus is on systems composed of modules, each of which is modelled by a finite state machine. In this context, a test of a system corresponds to a path in a directed graph representing the system. We are interested in finding a small set of tests with a desired fault coverage for a system. We formulate this problem using network flows, and discuss approximation algorithms and hardness results for it.

This is joint work with Mihalis Yannakakis.