5 citations · 12 across the 6 of their papers we have counts for
7 papers · 1 filter
Computing the Ehrhart quasi-polynomial of a rational simplex
Alexander Barvinok
We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms wer…
Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables
Alexander Barvinok
We represent the number of mxn non-negative integer matrices (contingency tables) with prescribed row sums and column sums as the expected value of the permanent of a non-negative…
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry
Alexander Barvinok, Alex Samorodnitsky
For a family X of k-subsets of the set 1,...,n, let |X| be the cardinality of X and let Gamma(X,mu) be the expected maximum weight of a subset from X when the weights of 1,...,n ar…
Short rational generating functions for lattice point problems
Alexander Barvinok, Kevin Woods
We prove that for any fixed d the generating function of the projection of the set of integer points in a rational d-dimensional polytope can be computed in polynomial time. As a c…
The distribution of values in the quadratic assignment problem
Alexander Barvinok, Tamon Stephen
We obtain a number of results regarding the distribution of values of a quadratic function f on the set of nxn permutation matrices (identified with the symmetric group S_n) around…
New Permanent Estimators via Non-Commutative Determinants
Alexander Barvinok
We introduce a new notion of the determinant, called symmetrized determinant, for a square matrix with the entries in an associative algebra . The monomial expansion of the symm…