2005/02/14 by Alexander Barvinok, Barvinok, Alexander
Computer Science · Mathematics · #60D05 #68W20 #68W25 #90C26 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Point processes and geometric inequalities #math.CO #math.OC #msc:60D05 #msc:68W20 #msc:68W25 #msc:90C26
paper · pdf · doi:10.48550/arxiv.math/0502298
15 pages
arxiv created 2005/02/14 · openalex publication_date 2005/02/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of efficient integration of an n-variate polynomial with respect to the Gaussian measure in Rn 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 fp 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.