Dr. Schulman's research will tackle two problems of central importance in computer science: (1) Linear programming in strongly polynomial time and (2) Matrix pre-conditioning by diagonal balancing. A strongly polynomial-time algorithm for linear programming would be a breakthrough in complexity theory over the real field. It may lead to improved algorithms for harder types of convex programming (e.g., semidefinite) which (albeit in polynomial time) are currently prohibitively slow. Better algorithms for matrix preconditioning have the potentially to significantly improve linear algebra software packages.
Among the primary outcomes of this research project is the first successful run-time analysis of an important algorithm used in numerical linear algebra. This algorithm, introduced in its basic form by Osborne in 1960, is widely deployed in leading numerical software packages (e.g., EISPACK/LAPACK). These packages are widely used in scientific, government and business applications, so progress in the underlying algorithms can have wide impact. This particular algorithm performs "pre-conditioning" of an input matrix, in order that subsequent algebraic operations (particularly eigenvalue calculation) will incur minimal numerical error. The algorithm is a simple iterative scheme, and in practice it generally outruns more complicated combinatorial algorithms that were designed decades later. However, ever since its introduction it has eluded run-time guarantees. We have now finally proven that a version of the algorithm runs in time O(n^4), for a broad class of n by n matrices, thus establishing the first firm theoretical basis for the empirical success of the method. We hope this work (which has just been submitted for publication) will lead to even stronger theoretical bounds, and to experimentation with the variations of the algorithm that were fruitful in the theoretical analysis. In other work: (a) We designed a new class of real-time error-correcting codes ("tree codes") based on a novel conjecture in analytic number theory. This has potential future impact in ensuring the reliability of rapid interactive communications among automated distributed agents. (b) We have obtained new algorithms as well as hardness results for certain problems in algorithmic game theory, in which the designer of a network (whether physical or digital) wishes to minimize construction budget, whilst ensuring that the equilibrium generated by the users (as they compete for network capacity) is favorable (delivers traffic quickly). A postdoctoral fellow was mentored on this project. (c) We have provided three advances in the general area of analysis of "big data": (c1) In the area of "topic models", which are commonly used to model a variety of key problems in learning theory, we obtained tight positive and negative results on the "sampling aperture" required in order to learn mixtures of unstructured distributions on large sets. This is a significant step within the rapidly advancing subfield studying mixture models and de-convolution -type problems; these problems have many scientific, government and business applications. (c2) One of the stumbling blocks in empirical statistical work is that of "incomplete data" (a.k.a. "missing data"). This problem cannot be addressed within a purely probabilistic framework except under very strong assumptions which do not usually hold in practice. In earlier work we proposed a geometric optimization approach to the incomplete data issue; this led naturally to certain computational problems on the clustering of affine subspaces. Under this award we studied these problems and obtained in various parameter regimes both algorithms and hardness results. This was joint work with a student. (c3) Jointly with a postdoc, we showed how to find small "core sets", or equivalently perform "functional data compression", for clustering problems in which the cluster centers have weights, a complication which arises naturally in several scenarios. (d) Maximal inequalities in function spaces such as L^p(R^d) have been a core topic in functional analysis for almost a century. Motivated by analysis of a class of algorithms for MAX 2CSP problems, we conjectured and then also proved an analogous maximal inequality for the space L^2(I) where I is the hypercube of any dimension. (One of the co-authors was a postdoc at the time of the work.) This work has already been followed up on and generalized by analysts. A variety of other results were supported by the award.
