A. Barvinok

activity

19972022

most citedNew Permanent Estimators via Non-Commutative Determinants

20 citations · 138 across the 47 of their papers we have counts for

collaborators

57 papers

math.NA2022

Computing the theta function

Alexander Barvinok

Let $f : R^{n} ⟶ R$ be a positive definite quadratic form and let $y \in R^{n}$ be a point. We present a fully polynomial randomized approximation sch…

math.MG2021

A quick estimate for the volume of a polyhedron

Alexander Barvinok, Mark Rudelson

Let $P$ be a bounded polyhedron defined as the intersection of the non-negative orthant $R_{+}^{n}$ and an affine subspace of codimension $m$ in $R^{n}$ . We show that a sim…

math.OC2021

When a system of real quadratic equations has a solution

Alexander Barvinok, Mark Rudelson

We provide a sufficient condition for solvability of a system of real quadratic equations $p_{i} (x) = y_{i}$ , $i = 1, \dots, m$ , where $p_{i} : R^{n} ⟶ R$ are…

math.CO2021

Smoothed counting of 0-1 points in polyhedra

Alexander Barvinok

Given a system of linear equations $ℓ_{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\righ…

math.OC2020

Testing systems of real quadratic equations for approximate solutions

Alexander Barvinok

Consider systems of equations $q_{i} (x) = 0$ , where $q_{i} : R^{n} ⟶ R$ , $i = 1, \dots, m$ , are quadratic forms. Our goal is to tell efficiently systems with many…

cs.DS2020

A remark on approximating permanents of positive definite matrices

Alexander Barvinok

Let $A$ be an $n \times n$ positive definite Hermitian matrix with all eigenvalues between 1 and 2. We represent the permanent of $A$ as the integral of some explicit log-concave f…