Konrad Anand
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Konrad Anand has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Mark Jerrum
University of London
2 shared publications - Graham Freifeld
School of Informatics University of Edinburgh United Kingdom
1 shared publication - Heng Guo
UIUC ETH Zürich UIUC UIUC UIUC UIUC ETH Zürich University of Edinburgh ETH Zürich UIUC
1 shared publication - Jiaheng Wang
Faculty of Informatics and Data Science University of Regensburg Germany
1 shared publication - Weiming Feng
University of Hong Kong, Hong Kong, Hong Kong
1 shared publication
Latest Publications
- Open Access
- 13 January 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Approximate Counting for Spin Systems in Sub-Quadratic Time
We present two randomised approximate counting algorithms with $\widetilde{O}(n^{2-c}/\varepsilon^2)$ running time for some constant $c>0$ and accuracy $\varepsilon$: (1) for the hard-core model with fugacity $\lambda$ on graphs with maximum degree $\Delta$ when $\lambda=O(\Delta^{-1.5-c_1})$ where $c_1=c/(2-2c)$; (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as $\mathbb{Z}^2$. For the hard-core model, Weitz's algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when $\lambda = o(\Delta^{-2})$. Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as $\mathbb{Z}^d$, but with a running time of the form $\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant.Comment: 27 pages. This is the TheoretiCS journal version- 13 January 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Open AccessApproximate Counting for Spin Systems in Sub-Quadratic Time
We present two randomised approximate counting algorithms with $\widetilde{O}(n^{2-c}/\varepsilon^2)$ running time for some constant $c>0$ and accuracy $\varepsilon$: (1) for the hard-core model with fugacity $\lambda$ on graphs with maximum degree $\Delta$ when $\lambda=O(\Delta^{-1.5-c_1})$ where $c_1=c/(2-2c)$; (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as $\mathbb{Z}^2$. For the hard-core model, Weitz's algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when $\lambda = o(\Delta^{-2})$. Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as $\mathbb{Z}^d$, but with a running time of the form $\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant.Comment: 27 pages. This is the TheoretiCS journal version - 2 August 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 13 (1) , 165-189
Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixingWe present a perfect marginal sampler of the unique Gibbs measure of a spin system on \mathbb{Z}^{2} . The algorithm is an adaptation of a previous “lazy depth-first” approach by the authors, but relaxes the requirement of strong spatial mixing to weak. Our result is a step towards methods of efficient sampling using only weak spatial mixing.The work exploits a classical result in statistical physics relating weak spatial mixing on \mathbb{Z}^{2} to strong spatial mixing on squares. When the spin system exhibits weak spatial mixing, the run-time of our sampler is linear in the size of sample. Applications of note are the ferromagnetic Potts model at supercritical temperatures and the ferromagnetic Ising model with consistent non-zero external field at any non-zero temperature.
- 2 August 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 13 (1) , 165-189
Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixingWe present a perfect marginal sampler of the unique Gibbs measure of a spin system on \mathbb{Z}^{2} . The algorithm is an adaptation of a previous “lazy depth-first” approach by the authors, but relaxes the requirement of strong spatial mixing to weak. Our result is a step towards methods of efficient sampling using only weak spatial mixing.The work exploits a classical result in statistical physics relating weak spatial mixing on \mathbb{Z}^{2} to strong spatial mixing on squares. When the spin system exhibits weak spatial mixing, the run-time of our sampler is linear in the size of sample. Applications of note are the ferromagnetic Potts model at supercritical temperatures and the ferromagnetic Ising model with consistent non-zero external field at any non-zero temperature.
- 26 July 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 51 (4) , 1280-1295
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.- 26 July 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 51 (4) , 1280-1295
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.