Title: RANDOMIZED POLYNOMIAL TIME ALGORITHMS TO APPROXIMATE THE PERMANENT WITHIN A SIMPLY EXPONENTIAL FACTOR

Abstract: I am planning to discuss recent randomized polynomial time algorithms that approximate the permanent of a nxn non-negative matrix, and, more generally, the mixed discriminant of n positive semidefinite nxn matrices within a (const)^n factor. Currently, the best randomized polynomial time algorithm approximates the permanent of a given nxn non-negative matrix within a factor of (1.32)^n.

Title: GENERALIZED MATRIX SCALING, COMBINATORIAL GAMES AND OTHER APPLICATIONS

Abstract: We consider a game with the set {X_1, X_2,..,X_p} as the pure strategies set for the first player, and the set {Y_1, Y_2,..,Y_q} as the pure strategies set for the second player (X_i are non-negative vectors in R^k, and Y_j are non-negative vectors in R^l). Let H be a k * l- matrix, and we define the payoff for the first player as (X_i,H Y_j), if the players use their strategies X_i and Y_j respectively. Usually we apply this framework to games with strategy sets of combinatorial nature, therefore we term such games "combinatorial games". The numbers p and q are assumed to be much bigger than k and l. We are interested to find optimal mixed strategies of the game which may be described by a small number of parameters. In particular, a product form is considered when the probability of a pure strategy is represented as a product of factors dependent on only one component of the strategy. To get such a representation we use a generalized matrix scaling and generalized permanents. The necessary and sufficient condition for the existence of such representations is established.

Title: OPERATOR MATCHING, SCALING and SINKHORN's ITERATION.

Abstract: We consider nonnegative linear operators acting on a linear space of real or complex n by n matrices. Such an operator T is called nonnegative if the cone of all semidefinite matrices is invariant with respect to T.

First, we introduce notions which generalize "matching" properties of nonnegative (entry-wise) matrices to nonnegative operators.

Next, we introduce operator scaling and the operator Sinkhorn iteration. Having in mind a probabilistic meaning of the usual Sinkhorn iteration, one can view the proposed generalization as a quantum analog.

The rest of the talk will be about various convergence properties of the operator Sinkhorn iteration and its applications, such as approximations of mixed determinants, non-convex optimization and generalized Alexandrov-Fenchel inequalities.

We also plan to introduce a strange construction which pretends to be an operator/quantum analog of usual permanents. At the end of the talk, we speculate on what might be called "quantum matching".

We will present in details a polynomial-time algorithm to approximate mixed discriminant with accuracy matching this of the best known randomized algorithms. A key result, which makes this algorithm possible, is the proof of Bapat's conjecture:

Let $A_1,...,A_n$ be $n$ positive semidefinite matrices with unit traces, and assume that the sum of these matrices is the identity matrix. Then the mixed discriminant $D(A_1,...A_n)$ is at least $n!/n^n$.

In the special case when all the matrices are diagonal we obtain the famous van der Waerden conjecture stating that a permanent of a doubly stochastic matrix is at least $n!/n^n$. Our proof is a generalization of the Falikman - Egorychev proofs of this conjecture.

Title: MATRIX SCALING OVER CONVEX CONES AND DUALITIES AND THEIR APPLICATIONS IN MATHEMATICAL PROGRAMMING

Abstract: Doubly stochastic scaling of nonnegative matrices is a fundamental old problem. However, the study of doubly quasi-stochastic scaling of general matrices became of interest much later and was inspired by Karmarkar's famous linear programming algorithm in which diagonal scaling played a key role. In particular, diagonal scaling of positive semidefinite symmetric matrices is closely related to LP. This is because of two reasons. Firstly, LP can be converted into the problem of testing if a convex quadratic form, f(x), has a nontrivial zero over the cone of nonnegative vectors, K. Secondly, the following ``duality'' holds: f(x) has a nontrivial zero over K if and only if its Hessian is not diagonally scalable. In this talk we first define the scaling problem in much more generality, by replacing K with an arbitrary closed convex pointed cone of a given subspace, and f(x) by an arbitrary smooth homogeneous function. We establish several dualities for this general scaling problem, called scaling dualities, relating the scalability of f(x) to the existence of its nontrivial zero over K. The latter zero-finding problem, called homogeneous programming, which can be viewed as a generalization of Karmarkar's LP formulation is a fundamental canonical problem in mathematical programming. Using scaling dualities, results from Nesterov and Nemirovski's self-concordance theory, and derivation of several bounds, we describe potential-reduction and path-following algorithms that not only give new polynomial-time algorithms for many convex programming problems (e.g. conic LP over symmetric cones such as LP and semidefinite programming), but also are capable of solving general scaling problems. We also use the scaling dualities to derive generalization of the arithmetic-geometric mean and Hadamard inequalities. Finally, the application of the scaling problem and scaling dualities in non-convex programming and in solving NP-complete problems will be considered.

Title: MATRIX SCALING: EXISTENCE AND COMPUTATION

Abstract: A scaling of a matrix A is a matrix of the form XAY where X and Y are nonnegative diagonal matrices. Scaling problems concern the identification of scalings of given matrices which have prescribed properties. Results about existence, characterization and computation of a variety of scaling problems will be discussed, with emphasis on complexity analysis of methods that compute approximate solutions. Joint work with Arkadi Nemirovski.

Title: SCALING IN APPROXIMATION ALGORITHMS.

Abstract: We briefly describe two applications of scaling - in approximation of the permanent and in approximation of the mixed discriminant. Our main focus will be on several seemingly new questions these applications suggest. This stems from a joint work with Leonid Gurvits, Nati Linial and Avi Wigderson.