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

Showing 2018Show all

4 papers · 1 filter

math.CO2018

Searching for dense subsets in a graph via the partition function

Alexander Barvinok, Anthony Della Pella

For a set $S$ of vertices of a graph $G$ , we define its density $0 \leq σ (S) \leq 1$ as the ratio of the number of edges of $G$ spanned by the vertices of $S$ to $(2 ∣ S ∣)$ .…

math.CO2018★ 3 cited

Approximating real-rooted and stable polynomials, with combinatorial applications

Alexander Barvinok

Let $p (x) = a_{0} + a_{1} x + \dots + a_{n} x^{n}$ be a polynomial with all roots real and satisfying $x \leq - δ$ for some $0 < δ < 1$ . We show that for any $0 < ε < 1$ , the value of $p (1)$ is de…

cs.DS2018

Stability and complexity of mixed discriminants

Alexander Barvinok

We show that the mixed discriminant of $n$ positive semidefinite $n \times n$ real symmetric matrices can be approximated within a relative error $ε > 0$ in quasi-polynomial $n^{O(\l…

math.CO2018

Computing permanents of complex diagonally dominant matrices and tensors

Alexander Barvinok

We prove that for any $λ > 1$ , fixed in advance, the permanent of an $n \times n$ complex matrix, where the absolute value of each diagonal entry is at least $λ$ times bigger than t…