Zobrazeno 1 - 10
of 434
pro vyhledávání: '"Goebel, Andreas"'
Autor:
Göbel, Andreas, Pappik, Marcus
We show that, under mild assumptions, every distribution on the hypercube $\{0, 1\}^{n}$ that admits a polynomial-time Markov chain approximate sampler also has an exact sampling algorithm with expected running time in poly$(n)$.
Comment: 12 pag
Comment: 12 pag
Externí odkaz:
http://arxiv.org/abs/2410.00882
We investigate the complexity of parameterised holant problems $\textsc{p-Holant}(\mathcal{S})$ for families of signatures~$\mathcal{S}$. The parameterised holant framework was introduced by Curticapean in 2015 as a counter-part to the classical theo
Externí odkaz:
http://arxiv.org/abs/2409.13579
We prove that for every locally stable and tempered pair potential $\phi$ with bounded range, there exists a unique infinite-volume Gibbs point process on $\mathbb{R}^d$ for every activity $\lambda < (e^{L} \hat{C}_{\phi})^{-1}$, where $L$ is the loc
Externí odkaz:
http://arxiv.org/abs/2407.01321
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become sa
Externí odkaz:
http://arxiv.org/abs/2401.10818
The Weisfeiler-Leman (WL) dimension of a graph parameter $f$ is the minimum $k$ such that, if $G_1$ and $G_2$ are indistinguishable by the $k$-dimensional WL-algorithm then $f(G_1)=f(G_2)$. The WL-dimension of $f$ is $\infty$ if no such $k$ exists. W
Externí odkaz:
http://arxiv.org/abs/2310.19006
We provide a perfect sampling algorithm for the hard-sphere model on subsets of $\mathbb{R}^d$ with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithm
Externí odkaz:
http://arxiv.org/abs/2305.02450
Detecting the dimensionality of graphs is a central topic in machine learning. While the problem has been tackled empirically as well as theoretically, existing methods have several drawbacks. On the one hand, empirical tools are computationally heav
Externí odkaz:
http://arxiv.org/abs/2302.06357
Publikováno v:
SIAM Journal on Discrete Mathematics, Vol. 38, Iss. 2 (2024)
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inho
Externí odkaz:
http://arxiv.org/abs/2302.04113
We study the SIRS process, a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its su
Externí odkaz:
http://arxiv.org/abs/2205.02653
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-
Externí odkaz:
http://arxiv.org/abs/2204.01793