About

Alexander Barvinok is a tenured faculty member in the Department of Mathematics at the University of Michigan. He holds a Ph.D. from Leningrad State, obtained in 1988. His research interests include computational complexity and algorithms in algebra, geometry, and combinatorics. Currently, he is particularly focused on the connections between various notions of phase transition in statistical physics, the analytical properties of partition functions, and computational complexity.

Research topics

• Physics
• Mathematics
• Combinatorics
• Discrete mathematics
• Quantum mechanics
• Mathematical analysis

Selected publications

• A quick estimate for the volume of a polyhedron

  Israel Journal of Mathematics · 2024-04-24

  preprintOpen access1st authorCorresponding
  PublisherOA PDFDOI

• On the zeros of partition functions with multi-spin interactions

  arXiv (Cornell University) · 2024-06-06

  preprintOpen access1st authorCorresponding

  Let $X_1, \ldots, X_n$ be probability spaces, let $X$ be their direct product, let $ϕ_1, \ldots, ϕ_m: X \longrightarrow {\Bbb C}$ be random variables, each depending only on a few coordinates of a point $x=(x_1, \ldots, x_n)$, and let $f=ϕ_1 + \ldots + ϕ_m$. The expectation $E\thinspace e^{λf}$, where $λ\in {\Bbb C}$, appears in statistical physics as the partition function of a system with multi-spin interactions, and also in combinatorics and computer science, where it is known as the partition function of edge-coloring models, tensor network contractions or a Holant polynomial. Assuming that each $ϕ_i$ is 1-Lipschitz in the Hamming metric of $X$, that each $ϕ_i(x)$ depends on at most $r \geq 2$ coordinates $x_1, \ldots, x_n$ of $x \in X$, and that for each $j$ there are at most $c \geq 1$ functions $ϕ_i$ that depend on the coordinate $x_j$, we prove that $E\thinspace e^{λf} \ne 0$ provided $| λ| \leq \ (3 c \sqrt{r-1})^{-1}$ and that the bound is sharp up to a constant factor. Taking a scaling limit, we prove a similar result for functions $ϕ_1, \ldots, ϕ_m: {\Bbb R}^n \longrightarrow {\Bbb C}$ that are 1-Lipschitz in the $\ell^1$ metric of ${\Bbb R}^n$ and where the expectation is taken with respect to the standard Gaussian measure in ${\Bbb R}^n$. As a corollary, the value of the expectation can be efficiently approximated, provided $λ$ lies in a slightly smaller disc.

  PublisherOA PDFDOI

• Integrating Products of Quadratic Forms

  Discrete & Computational Geometry · 2023-08-02 · 1 citations

  article1st authorCorresponding
  PublisherDOI

• Computing the theta function

  arXiv (Cornell University) · 2022-08-10

  preprintOpen access1st authorCorresponding

  Let $f: {\Bbb R}^n \longrightarrow {\Bbb R}$ be a positive definite quadratic form and let $y \in {\Bbb R}^n$ be a point. We present a fully polynomial randomized approximation scheme (FPRAS) for computing $\sum_{x \in {\Bbb Z}^n} e^{-f(x)}$, provided the eigenvalues of $f$ lie in the interval roughly between $s$ and $e^{s}$ and for computing $\sum_{x \in {\Bbb Z}^n} e^{-f(x-y)}$, provided the eigenvalues of $f$ lie in the interval roughly between $e^{-s}$ and $s^{-1}$ for some $s \geq 3$. To compute the first sum, we represent it as the integral of an explicit log-concave function on ${\Bbb R}^n$, and to compute the second sum, we use the reciprocity relation for theta functions. We then apply our results to test the existence of many short integer vectors in a given subspace $L \subset {\Bbb R}^n$, to estimate the distance from a given point to a lattice, and to sample a random lattice point from the discrete Gaussian distribution.

  PublisherOA PDFDOI

• Smoothed counting of 0–1 points in polyhedra

  Random Structures and Algorithms · 2022-12-30

  articleOpen access1st authorCorresponding

  Abstract Given a system of linear equations in an ‐vector of 0–1 variables, we compute the expectation of , where is a vector of independent Bernoulli random variables and are constants. The algorithm runs in quasi‐polynomial time under some sparseness condition on the matrix of the system. The result is based on the absence of the zeros of the analytic continuation of the expectation for complex probabilities, which can also be interpreted as the absence of a phase transition in the Ising model with a sufficiently strong external field. We discuss applications to perfect matchings in hypergraphs and randomized rounding in discrete optimization.

  PublisherOA PDFDOI

• When a system of real quadratic equations has a solution

  Advances in Mathematics · 2022-04-15 · 4 citations

  article1st authorCorresponding
  PublisherDOI

• When a system of real quadratic equations has a solution

  arXiv (Cornell University) · 2021-06-15

  preprintOpen access1st authorCorresponding

  We provide a sufficient condition for solvability of a system of real quadratic equations $p_i(x)=y_i$, $i=1, \ldots, m$, where $p_i: {\mathbb R}^n \longrightarrow {\mathbb R}$ are quadratic forms. By solving a positive semidefinite program, one can reduce it to another system of the type $q_i(x)=α_i$, $i=1, \ldots, m$, where $q_i: {\mathbb R}^n \longrightarrow {\mathbb R}$ are quadratic forms and $α_i=\mathrm{tr\ } q_i$. We prove that the latter system has solution $x \in {\mathbb R}^n$ if for some (equivalently, for any) orthonormal basis $A_1,\ldots, A_m$ in the space spanned by the matrices of the forms $q_i$, the operator norm of $A_1^2 + \ldots + A_m^2$ does not exceed $η/m$ for some absolute constant $η> 0$. The condition can be checked in polynomial time and is satisfied, for example, for random $q_i$ provided $m \leq γ\sqrt{n}$ for an absolute constant $γ>0$. We prove a similar sufficient condition for a system of homogeneous quadratic equations to have a non-trivial solution. While the condition we obtain is of an algebraic nature, the proof relies on analytic tools including Fourier analysis and measure concentration.

  PublisherOA PDFDOI

• More on zeros and approximation of the Ising partition function

  Forum of Mathematics Sigma · 2021 · 5 citations

  1st authorCorresponding
  • Mathematics
  • Combinatorics
  • Discrete mathematics

  Abstract We consider the problem of computing the partition function $\sum _x e^{f(x)}$ , where $f: \{-1, 1\}^n \longrightarrow {\mathbb R}$ is a quadratic or cubic polynomial on the Boolean cube $\{-1, 1\}^n$ . In the case of a quadratic polynomial f , we show that the partition function can be approximated within relative error $0 < \epsilon < 1$ in quasi-polynomial $n^{O(\ln n - \ln \epsilon )}$ time if the Lipschitz constant of the non-linear part of f with respect to the $\ell ^1$ metric on the Boolean cube does not exceed $1-\delta $ , for any $\delta>0$ , fixed in advance. For a cubic polynomial f , we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $\sum _x e^{\tilde {f}(x)} \ne 0$ for complex-valued polynomials $\tilde {f}$ in a neighborhood of a real-valued f satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zero-free region are interpreted as the absence of a phase transition in the Lee–Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but not every single interaction of sets of vertices.

  PublisherOA PDFDOI

• Smoothed counting of 0-1 points in polyhedra

  arXiv (Cornell University) · 2021-03-09

  preprintOpen access1st authorCorresponding

  Given a system of linear equations $\ell_i(x)=β_i$ in an $n$-vector $x$ of 0-1 variables, we compute the expectation of $\exp\left\{- \sum_i γ_i \left(\ell_i(x) - β_i\right)^2\right\}$, where $x$ is a vector of independent Bernoulli random variables and $γ_i >0$ are constants. The algorithm runs in quasi-polynomial $n^{O(\ln n)}$ time under some sparseness condition on the matrix of the system. The result is based on the absence of the zeros of the analytic continuation of the expectation for complex probabilities, which can also be interpreted as the absence of a phase transition in the Ising model with a sufficiently strong external field. We discuss applications to (perfect) matchings in hypergraphs and randomized rounding in discrete optimization.

  PublisherOA PDFDOI

• When the positive semidefinite relaxation guarantees a solution to a system of real quadratic equations.

  arXiv (Cornell University) · 2021-06-15

  preprintOpen access1st authorCorresponding

  By solving a positive semidefinite program, one can reduce a system of real quadratic equations to a system of the type $q_i(x)=\alpha_i$, $i=1, \ldots, m$, where $q_i: {\Bbb R}^n \longrightarrow {\Bbb R}$ are quadratic forms and $\alpha_i=\operatorname{trace} q_i$. We prove a sufficient condition for the latter system to have a solution $x \in {\Bbb R}^n$: assuming that the operator norms of the $n \times n$ matrices $Q_i$ of $q_i$ do not exceed 1, the smallest eigenvalue the $m \times m$ matrix with the $(i,j)$-th entry equal $\operatorname{tr} (Q_i Q_j)$ is at least $\gamma n^{2/3} m^2 \ln n$ for an absolute constant $\gamma >0$. In particular, this happens when $n \gg m^6$ and the forms $q_i$ are sufficiently generic. We prove a similar sufficient condition for a homogeneous system of quadratic equations to have a non-trivial solution.

  Publisher

Recent grants

• Computing Partition Functions in Hard Problems of Combinatorial Enumeration and Optimization

  NSF · $380k · 2014–2019

• Combinatorics, Complexity and Complex Zeros of Partition Functions

  NSF · $350k · 2019–2025

• Combinatorics, Geometry, and Algorithms

  NSF · $556k · 2009–2015

• Complexity in Geometric Combinatorics

  NSF · $400k · 2004–2011

Frequent coauthors

• Alex Samorodnitsky

  Hebrew University of Jerusalem

  11 shared

• Isabella Novik

  University of Washington

  11 shared

• J. A. Hartigan

  New York State Department of Health

  8 shared

• Pablo Soberón

  6 shared

• Mark Rudelson

  University of Michigan–Ann Arbor

  5 shared

• Seung Jin Lee

  4 shared

• Alexander Yong

  3 shared

• Gerhard J. Woeginger

  RWTH Aachen University

  3 shared

Labs

• U-M LSA MathematicsPI