3 citations · 3 across the 1 of their papers we have counts for
3 papers
cs.DM2020★ 3 cited
PTAS for Sparse General-Valued CSPs
Balázs F. Mezei, Marcin Wrochna, Stanislav Živný
We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes.…
math.CO2020
The Ising antiferromagnet and max cut on random regular graphs
Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei +1
The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of momen…
math.CO2019
Successive shortest paths in complete graphs with random edge weights
Stefanie Gerke, Balázs F. Mezei, Gregory B. Sorkin
Consider a complete graph with edge weights drawn independently from a uniform distribution . The weight of the shortest (minimum-weight) path between two given…