Integration and Optimization of Multivariate Polynomials by Restriction onto a Random Subspace

We consider the problem of efficient integration of an n-variate polynomial with respect to the Gaussian measure in ℝⁿ and related problems of complex integration and optimization of a polynomial on the unit sphere. We identify a class of n-variate polynomials f for which the integral of any positive integer power f^p over the whole space is well approximated by a properly scaled integral over a random subspace of dimension O(log n). Consequently, the maximum of f on the unit sphere is well approximated by a properly scaled maximum on the unit sphere in a random subspace of dimension O(log n). We discuss connections with problems of combinatorial counting and applications to efficient approximation of a hafnian of a positive matrix.     

Centrally symmetric polytopes with many faces

We present explicit constructions of centrally symmetric polytopes with many faces: (1) we construct a d-dimensional centrally symmetric polytope P with about 3 ^d/4 ≈ (1.316) ^d vertices such that every pair of non-antipodal vertices of P spans an edge of P, (2) for an integer k ≥ 2, we construct a d-dimensional centrally symmetric polytope P of an arbitrarily high dimension d and with an arbitrarily large number N of vertices such that for some 0 < δ _k < 1 at least (1 ? (δ _k ) ^d )( _k ^N ) k-subsets of the set of vertices span faces of P, and (3) for an integer k ≥ 2 and α > 0, we construct a centrally symmetric polytope Q with an arbitrarily large number of vertices N and of dimension d = k ^1+o(1) such that at least $(1 - k^{ - \alpha } )(_k^N )$ k-subsets of the set of vertices span faces of Q.     

Approximate counting via random optimization

Let ℱ_n be a family of subsets of {1,…,n}. We propose a simple randomized algorithm to estimate the cardinality of ℱ_n from the maximum weight of a subset X∈ℱ_n in a random weighting of {1,…,n}. The examples include enumeration of perfect matchings in graphs, bases in matroids, and Hamiltonian cycles in graphs. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 187–198 (1997)     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

Short rational generating functions for lattice point problems

We prove that for any fixed the generating function of the projection of the set of integer points in a rational -dimensional polytope can be computed in polynomial time. As a corollary, we deduce that various interesting sets of lattice points, notably integer semigroups and (minimal) Hilbert bases of rational cones, have short rational generating functions provided certain parameters (the dimension and the number of generators) are fixed. It follows then that many computational problems for such sets (for example, finding the number of positive integers not representable as a non-negative integer combination of given coprime positive integers ) admit polynomial time algorithms. We also discuss a related problem of computing the Hilbert series of a ring generated by monomials.

     

Homological type of spaces of configurations of structurally stable type in C2

Mathematical Notes -     

Random weighting,asymptotic counting,and inverse isoperimetry

For a family X of k-subsets of the set {1, …, n}, let |X| be the cardinality of X and let Γ(X, μ) be the expected maximum weight of a subset from X when the weights of 1, …, n are chosen independently at random from a symmetric probability distribution μ on ℝ. We consider the inverse isoperimetric problem of finding μ for which Γ(X, μ) gives the best estimate of ln |X|. We prove that the optimal choice of μ is the logistic distribution, in which case Γ(X, μ) provides an asymptotically tight estimate of ln |X| as k ⁻¹ ln |X} grows. Since in many important cases Γ(X, μ) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems. Given μ, we describe families X of a given cardinality with the minimum value of Γ(X, μ), thus extending and sharpening various isoperimetric inequalities in the Boolean cube. The research of the first author was partially supported by NSF Grants DMS 9734138 and DMS 0400617. The research of the second author was partially supported by ISF Grant 039-7165 and by GIF grant I-2052.     

The distance approach to approximate combinatorial counting

We develop general methods to obtain fast (polynomial time) estimates of the cardinality of a combinatorially defined set via solving some randomly generated optimization problems on the set. Examples include enumeration of perfect matchings in a graph, linearly independent subsets of a set of vectors and colored spanning subgraphs of a graph. Geometrically, we estimate the cardinality of a subset of the Boolean cube via the average distance from a point in the cube to the subset with respect to some distance function. We derive asymptotically sharp cardinality bounds in the case of the Hamming distance and show that for small subsets a suitably defined “randomized” Hamming distance allows one to get tighter estimates of the cardinality. Submitted: June 2000, Revised version: January 2001.     

Measure concentration in optimization

We discuss some consequences of the measure concentration phenomenon for optimization and computational problems. Topics include average case analysis in optimization, efficient approximate counting, computation of mixed discriminants and permanents, and semidefinite relaxation in quadratic programming.