Georgia Institute of Technology College of Sciences

This is joint work with Alex Postnikov. Imagine that you are to build a system of space stations (graph vertices), which communicate via laser beams (edges). The edge directions were already chosen, but you must place the stations so that none of the beams miss their targets. In this talk, we let the edge directions be generic and independent, a choice that constrains vertex placement the most. For K_{3} in \mathbb{R}^{2}, the edges specify a unique triangle, but its size is arbitrary --- D_{2}(K_{3})=1 degree of freedom; we say that K_{3} is rigid in \mathbb{R}^{2}. We call D_{n}(G) the degree of parallel rigidity of the graph for generic edge directions. We found an elegant combinatorial characterization of D_{n}(G) --- it is equal to the minimal number of edges in the intersection of n spanning trees of G. In this talk, I will give a linear-algebraic proof of this result, and of some other properties of D_{n}(G). The notion of parallel graph rigidity was previously studied by Whiteley and Develin-Martin-Reiner. The papers worked with the generic parallel rigidity matroid; I will briefly compare our results in terms of D_{n}(G) with the previous work.

A shot noise process is essentially a compound Poisson process whereby the arriving shots are allowed to accumulate or decay after their arrival via some preset shot (impulse response) function. Shot noise models see applications in diverse areas such as insurance, fi- nance, hydrology, textile engineering, and electronics. This talk stud- ies several statistical inference issues for shot noise processes. Under mild conditions, ergodicity is proven in that process sample paths sat- isfy a strong law of large numbers and central limit theorem. These results have application in storage modeling. Shot function parameter estimation from a data history observed on a discrete-time lattice is then explored. Optimal estimating functions are tractable when the shot function satisfies a so-called interval similar condition. Moment methods of estimation are easily applicable if the shot function is com- pactly supported and show good performance. In all cases, asymptotic normality of the proposed estimators is established.

Scarf's lemma is one of the fundamental results in combinatorics, originally introduced to study the core of an N-person game. Over the last four decades, the usefulness of Scarf's lemma has been demonstrated in several important combinatorial problems seeking stable solutions. However, the complexity of the computational version of Scarf's lemma (Scarf) remained open. In this talk, I will prove that Scarf is complete for the complexity class PPAD. This shows that Scarf is as hard as the computational versions of Brouwer's fixed point theorem and Sperner's lemma. Hence, there is no polynomial-time algorithm for Scarf unless PPAD \subseteq P. I will also talk about fractional stable paths problem, finding fractional kernels in digraphs, finding fractional stable matching in hypergraphic preference systems and finding core in an N-person balanced game with non-transferable utilities. I will show the connection between these problems through Scarf's lemma and address the complexity of these problems.

In this talk I will describe recent work with C. N. Moore about the two-phase Stefan problem with a degenerate zone. We start with local solutions (no reference to initial or boundary data) and then obtain intrinsic energy estimates, that will in turn lead to the continuity of the temperature. We then show existence and uniqueness of solutions with signed measures as data. The uniqueness problem with signed measure data has been open for some 30 years for any degenerate parabolic equation.