Stanford Theory Lunch Speaker List
Winter 2004

Thursdays, 12:15pm, in the Theory Lounge (wing 4B in the Gates Computer Science building)

Schedule
 Jan 15 Don Knuth On asymptotics Jan 22 Jason Hartline, Microsoft Research On Seller Optimal Envy-Free Pricing Jan 29 Sergei Vassilvitskii Multiobjective Optimization: Finding All Relevant Solutions Feb 5 Man-Cho Anthony So Fritz John's Theorem Feb 12 Mathieu Turuani Complexity Results for the Protocol Insecurity Decision Problem Feb 19 Sriram Sankaranarayanan Checking polynomials for positive semi-definiteness Feb 26 Ho-Lin Chen Error-correction mechanisms for self assembly Mar 4 Aaron Bradley Affine Relationships Among Variables of a Program Mar 11 Damon Mosk-Aoyama Testing Modular Systems via Edge Covering Mar 18 Mihaela Presentation of the award for the best talk of the quarter

Abstracts
 Complex analysis methods 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. On Seller Optimal Envy-Free Pricing 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. Multiobjective Optimization: Finding All Relevant Solutions 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. Fritz John's Theorem 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. Complexity Results for the Protocol Insecurity Decision Problem 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 Checking polynomials for positive semi-definiteness 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. Error-correction mechanisms for self assembly 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. Affine Relationships Among Variables of a Program 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. Testing Modular Systems via Edge Covering 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.

(archive of past announcements will be here)