Smoothed counting of 0–1 points in polyhedra
Smoothed counting of 0–1 points in polyhedra
复制标题
多面体中 0-1 点的平滑计数
DOI：
10.1002/rsa.21135
复制
发表时间：
2022
影响因子：
1
通讯作者：
Barvinok, Alexander
中科院分区：
文献类型：
--
作者：
Barvinok, Alexander
Given a system of linear equations ℓi(x)=βi$$ {\ell}_i(x)={\beta}_i $$ in an n$$ n $$‐vector x$$ x $$ of 0–1 variables, we compute the expectation of exp−∑iγiℓi(x)−βi2$$ \exp \left\{-{\sum}_i{\gamma}_i{\left({\ell}_i(x)-{\beta}_i\right)}^2\right\} $$, where x$$ x $$ is a vector of independent Bernoulli random variables and γi>0$$ {\gamma}_i>0 $$ are constants. The algorithm runs in quasi‐polynomial nO(lnn)$$ {n}^{O\left(\ln n\right)} $$ 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.
Given a system of linear equations ℓi(x)=βi$$ {\ell}_i(x)={\beta}_i $$ in an n$$ n $$‐vector x$$ x $$ of 0–1 variables, we compute the expectation of exp−∑iγiℓi(x)−βi2$$ \exp \left\{-{\sum}_i{\gamma}_i{\left({\ell}_i(x)-{\beta}_i\right)}^2\right\} $$, where x$$ x $$ is a vector of independent Bernoulli random variables and γi>0$$ {\gamma}_i>0 $$ are constants. The algorithm runs in quasi‐polynomial nO(lnn)$$ {n}^{O\left(\ln n\right)} $$ 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.
登录
查看更多内容
(3, 3)-超图中匹配的近似计数
DOI：
--
发表时间：
2014
期刊：
Scandinavian Workshop on Algorithm Theory
影响因子：
--
作者：
A. Dudek;Marek Karpinski;A. Rucinski;Edyta Szymanska
通讯作者：
Edyta Szymanska
DOI：
--
发表时间：
2019
期刊：
OnIine journal of analytic combinatorics
影响因子：
--
作者：
Barvinok, Alexander
通讯作者：
Barvinok, Alexander
Steiner 三重系统数量的上限
DOI：
--
发表时间：
2011
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
N. Linial;Zur Luria
通讯作者：
Zur Luria
A·哈贝：（1989）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--
DOI：
10.1109/focs52979.2021.00023
发表时间：
2021-06
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda
通讯作者：
Zongchen Chen;Kuikui Liu;Eric Vigoda