Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Pjotr Buys

dblp:278/2997 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2021
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 83% Combinatorics and discrete mathematics · 17%

Topics — the 5 heaviest of 5, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › counting complexity
#p-hardness
0.512021
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs · SODA 2021
Computational complexity
hardness of approximation
0.512021
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs · SODA 2021
Computational complexity › counting complexity
partition function
0.512021
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs · SODA 2021
Combinatorics and discrete mathematics › statistical physics models
ising model
0.112021
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs · SODA 2021
Combinatorics and discrete mathematics
statistical physics models
0.112021
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs · SODA 2021

Methods — techniques the papers use, named apart from their topics

gadget construction · 0.5dynamical systems · 0.5
YearPublicationVenuePosition
2021 Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs
abstract
We study the computational complexity of approximating the partition function of the ferromagnetic Ising model in the Lee-Yang circle of zeros given by |λ| = 1, where λ is the external field of the model. Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all |λ| ≠ 1 by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens in the circular arc around λ = 1, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point λ = 1; in fact, our techniques apply more generally to the whole unit circle |λ| = 1. We show #P-hardness for approximating the partition function on graphs of maximum degree Δ when b, the edge-interaction parameter, is in the interval and λ is a non-real on the unit circle. This result contrasts with known approximation algorithms when , and shows that the Lee-Yang circle of zeros is computationally intractable, even on bounded-degree graphs. Our inapproximability result is based on constructing rooted tree gadgets via a detailed understanding of the underlying dynamical systems, which are further parameterised by the degree of the root. The ferromagnetic Ising model has radically different behaviour than previously considered anti-ferromagnetic models, and showing our #P-hardness results in the whole Lee-Yang circle requires a new high-level strategy to construct the gadgets. To this end, we devise an elaborate inductive procedure to construct the required gadgets by taking into account the dependence between the degree of the root of the tree and the magnitude of the derivative at the fixpoint of the corresponding dynamical system. The full version (with all proofs) is available on arXiv at arxiv.org/abs/2006.14828.
Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts
SODA1