4 Search Results for "Liu, Jingcheng"

Document
DOI: 10.4230/LIPIcs.ESA.2023.29
Effective Resistances in Non-Expander Graphs

Authors: Dongrun Cai, Xue Chen, and Pan Peng

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Effective resistances are ubiquitous in graph algorithms and network analysis. For an undirected graph G, its effective resistance R_G(s,t) between two vertices s and t is defined as the equivalent resistance between s and t if G is thought of as an electrical network with unit resistance on each edge. If we use L_G to denote the Laplacian matrix of G and L_G^† to denote its pseudo-inverse, we have R_G(s,t) = (𝟏_s-𝟏_t)^⊤ L^† (𝟏_s-𝟏_t) such that classical Laplacian solvers [Daniel A. Spielman and Shang{-}Hua Teng, 2014] provide almost-linear time algorithms to approximate R_G(s,t). In this work, we study sublinear time algorithms to approximate the effective resistance of an adjacent pair s and t. We consider the classical adjacency list model [Ron, 2019] for local algorithms. While recent works [Andoni et al., 2018; Peng et al., 2021; Li and Sachdeva, 2023] have provided sublinear time algorithms for expander graphs, we prove several lower bounds for general graphs of n vertices and m edges: 1) It needs Ω(n) queries to obtain 1.01-approximations of the effective resistance of an adjacent pair s and t, even for graphs of degree at most 3 except s and t. 2) For graphs of degree at most d and any parameter 𝓁, it needs Ω(m/𝓁) queries to obtain c ⋅ min{d,𝓁}-approximations where c > 0 is a universal constant. Moreover, we supplement the first lower bound by providing a sublinear time (1+ε)-approximation algorithm for graphs of degree 2 except the pair s and t. One of our technical ingredients is to bound the expansion of a graph in terms of the smallest non-trivial eigenvalue of its Laplacian matrix after removing edges. We discover a new lower bound on the eigenvalues of perturbed graphs (resp. perturbed matrices) by incorporating the effective resistance of the removed edge (resp. the leverage scores of the removed rows), which may be of independent interest.
Cite as

Dongrun Cai, Xue Chen, and Pan Peng. Effective Resistances in Non-Expander Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ESA.2023.29,
  author =	{Cai, Dongrun and Chen, Xue and Peng, Pan},
  title =	{{Effective Resistances in Non-Expander Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.29},
  URN =		{urn:nbn:de:0030-drops-186823},
  doi =		{10.4230/LIPIcs.ESA.2023.29},
  annote =	{Keywords: Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.96
Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems

Authors: Shuai Shao and Yuxin Sun

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study complex zeros of the partition function of 2-spin systems, viewed as a multivariate polynomial in terms of the edge interaction parameters and the uniform external field. We obtain new zero-free regions in which all these parameters are complex-valued. Crucially based on the zero-freeness, we are able to extend the existence of correlation decay to these complex regions from real parameters. As a consequence, we obtain an FPTAS for computing the partition function of 2-spin systems on graphs of bounded degree for these parameter settings. We introduce the contraction property as a unified sufficient condition to devise FPTAS via either Weitz’s algorithm or Barvinok’s algorithm. Our main technical contribution is a very simple but general approach to extend any real parameter of which the 2-spin system exhibits correlation decay to its complex neighborhood where the partition function is zero-free and correlation decay still exists. This result formally establishes the inherent connection between two distinct notions of phase transition for 2-spin systems: the existence of correlation decay and the zero-freeness of the partition function via a unified perspective, contraction.
Cite as

Shuai Shao and Yuxin Sun. Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 96:1-96:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{shao_et_al:LIPIcs.ICALP.2020.96,
  author =	{Shao, Shuai and Sun, Yuxin},
  title =	{{Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{96:1--96:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.96},
  URN =		{urn:nbn:de:0030-drops-125036},
  doi =		{10.4230/LIPIcs.ICALP.2020.96},
  annote =	{Keywords: 2-Spin system, Correlation decay, Zero-freeness, Phase transition, Contraction}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.55
Fisher Zeros and Correlation Decay in the Ising Model

Authors: Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
The Ising model originated in statistical physics as a means of studying phase transitions in magnets, and has been the object of intensive study for almost a century. Combinatorially, it can be viewed as a natural distribution over cuts in a graph, and it has also been widely studied in computer science, especially in the context of approximate counting and sampling. In this paper, we study the complex zeros of the partition function of the Ising model, viewed as a polynomial in the "interaction parameter"; these are known as Fisher zeros in light of their introduction by Fisher in 1965. While the zeros of the partition function as a polynomial in the "field" parameter have been extensively studied since the classical work of Lee and Yang, comparatively little is known about Fisher zeros. Our main result shows that the zero-field Ising model has no Fisher zeros in a complex neighborhood of the entire region of parameters where the model exhibits correlation decay. In addition to shedding light on Fisher zeros themselves, this result also establishes a formal connection between two distinct notions of phase transition for the Ising model: the absence of complex zeros (analyticity of the free energy, or the logarithm of the partition function) and decay of correlations with distance. We also discuss the consequences of our result for efficient deterministic approximation of the partition function. Our proof relies heavily on algorithmic techniques, notably Weitz's self-avoiding walk tree, and as such belongs to a growing body of work that uses algorithmic methods to resolve classical questions in statistical physics.
Cite as

Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. Fisher Zeros and Correlation Decay in the Ising Model. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 55:1-55:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2019.55,
  author =	{Liu, Jingcheng and Sinclair, Alistair and Srivastava, Piyush},
  title =	{{Fisher Zeros and Correlation Decay in the Ising Model}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{55:1--55:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.55},
  URN =		{urn:nbn:de:0030-drops-101483},
  doi =		{10.4230/LIPIcs.ITCS.2019.55},
  annote =	{Keywords: Ising model, zeros of polynomials, partition functions, approximate counting, phase transitions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.843
The Complexity of Ferromagnetic Two-spin Systems with External Fields

Authors: Jingcheng Liu, Pinyan Lu, and Chihao Zhang

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We study the approximability of computing the partition function for ferromagnetic two-state spin systems. The remarkable algorithm by Jerrum and Sinclair showed that there is a fully polynomial-time randomized approximation scheme (FPRAS) for the special ferromagnetic Ising model with any given uniform external field. Later, Goldberg and Jerrum proved that it is #BIS-hard for Ising model if we allow inconsistent external fields on different nodes. In contrast to these two results, we prove that for any ferromagnetic two-state spin systems except the Ising model, there exists a threshold for external fields beyond which the problem is #BIS-hard, even if the external field is uniform.
Cite as

Jingcheng Liu, Pinyan Lu, and Chihao Zhang. The Complexity of Ferromagnetic Two-spin Systems with External Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 843-856, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.APPROX-RANDOM.2014.843,
  author =	{Liu, Jingcheng and Lu, Pinyan and Zhang, Chihao},
  title =	{{The Complexity of Ferromagnetic Two-spin Systems with External Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{843--856},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.843},
  URN =		{urn:nbn:de:0030-drops-47428},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.843},
  annote =	{Keywords: Spin System, #BIS-hard, FPRAS}
}
  • Refine by Author
  • 2 Liu, Jingcheng
  • 1 Cai, Dongrun
  • 1 Chen, Xue
  • 1 Lu, Pinyan
  • 1 Peng, Pan
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 #BIS-hard
  • 1 2-Spin system
  • 1 Contraction
  • 1 Correlation decay
  • 1 Effective Resistance
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2014
  • 1 2019
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact