LIVIVO - Search results -

Search results

Result 1 - 10 of total 16

Search options

Book ; Online: Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems

Chen, Zongchen

2023

Abstract: We present a simple combinatorial framework for establishing approximate tensorization of variance and entropy in the setting of spin systems (a.k.a. undirected graphical models) based on balanced separators of the underlying graph. Such approximate ... ...

Abstract	We present a simple combinatorial framework for establishing approximate tensorization of variance and entropy in the setting of spin systems (a.k.a. undirected graphical models) based on balanced separators of the underlying graph. Such approximate tensorization results immediately imply as corollaries many important structural properties of the associated Gibbs distribution, in particular rapid mixing of the Glauber dynamics for sampling. We prove approximate tensorization by recursively establishing block factorization of variance and entropy with a small balanced separator of the graph. Our approach goes beyond the classical canonical path method for variance and the recent spectral independence approach, and allows us to obtain new rapid mixing results. As applications of our approach, we show that: 1. On graphs of treewidth $t$, the mixing time of the Glauber dynamics is $n^{O(t)}$, which recovers the recent results of Eppstein and Frishberg with improved exponents and simpler proofs; 2. On bounded-degree planar graphs, strong spatial mixing implies $\tilde{O}(n)$ mixing time of the Glauber dynamics, which gives a faster algorithm than the previous deterministic counting algorithm by Yin and Zhang.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Mathematics - Combinatorics ; Mathematics - Probability
Subject code	519
Publishing date	2023-07-16
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Fast Sampling of $b$-Matchings and $b$-Edge Covers

Chen, Zongchen / Gu, Yuzhou

2023

Abstract: For integer $b \ge 1$, a $b$-matching (resp. $b$-edge cover) of a graph $G=(V,E)$ is a subset $S\subseteq E$ of edges such that every vertex is incident with at most (resp. at least) $b$ edges from $S$. We prove that for any $b \ge 1$ the simple Glauber ... ...

Abstract	For integer $b \ge 1$, a $b$-matching (resp. $b$-edge cover) of a graph $G=(V,E)$ is a subset $S\subseteq E$ of edges such that every vertex is incident with at most (resp. at least) $b$ edges from $S$. We prove that for any $b \ge 1$ the simple Glauber dynamics for sampling (weighted) $b$-matchings and $b$-edge covers mixes in $O(n\log n)$ time on all $n$-vertex bounded-degree graphs. This significantly improves upon previous results which have worse running time and only work for $b$-matchings with $b \le 7$ and for $b$-edge covers with $b \le 2$. Moreover generally, we prove spectral independence for a broad class of binary symmetric Holant problems with log-concave signatures, including $b$-matchings, $b$-edge covers, and antiferromagnetic $2$-spin edge models. We hence deduce optimal mixing time of Glauber dynamics from spectral independence.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Mathematics - Combinatorics ; Mathematics - Probability
Subject code	519 ; 511
Publishing date	2023-04-27
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Influence Maximization in Ising Models

Chen, Zongchen / Mossel, Elchanan

2023

Abstract: Given a complex high-dimensional distribution over $\{\pm 1\}^n$, what is the best way to increase the expected number of $+1$'s by controlling the values of only a small number of variables? Such a problem is known as influence maximization and has been ...

Abstract	Given a complex high-dimensional distribution over $\{\pm 1\}^n$, what is the best way to increase the expected number of $+1$'s by controlling the values of only a small number of variables? Such a problem is known as influence maximization and has been widely studied in social networks, biology, and computer science. In this paper, we consider influence maximization on the Ising model which is a prototypical example of undirected graphical models and has wide applications in many real-world problems. We establish a sharp computational phase transition for influence maximization on sparse Ising models under a bounded budget: In the high-temperature regime, we give a linear-time algorithm for finding a small subset of variables and their values which achieve nearly optimal influence; In the low-temperature regime, we show that the influence maximization problem cannot be solved in polynomial time under commonly-believed complexity assumption. The critical temperature coincides with the tree uniqueness/non-uniqueness threshold for Ising models which is also a critical point for other computational problems including approximate sampling and counting.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Social and Information Networks ; Mathematics - Probability
Publishing date	2023-09-10
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Strong spatial mixing for colorings on trees and its algorithmic applications

Chen, Zongchen / Liu, Kuikui / Mani, Nitya / Moitra, Ankur

2023

Abstract: Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution ... ...

Abstract	Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper $q$-colorings on a $\Delta$-regular tree exhibits SSM whenever $q \ge \Delta+1$. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with $q$ colors, one would obtain an efficient sampler for $q$-colorings on all bounded-degree graphs via simple Markov chain algorithms. It is surprising that such a basic question is still open, even on trees, but then again it also highlights how much we still have to learn about random colorings. In this paper, we show the following: (1) For any $\Delta \ge 3$, SSM holds for random $q$-colorings on trees of maximum degree $\Delta$ whenever $q \ge \Delta + 3$. Thus we almost fully resolve the aforementioned conjecture. Our result substantially improves upon the previously best bound which requires $q \ge 1.59\Delta+\gamma^$ for an absolute constant $\gamma^ > 0$. (2) For any $\Delta\ge 3$ and girth $g = \Omega_\Delta(1)$, we establish optimal mixing of the Glauber dynamics for $q$-colorings on graphs of maximum degree $\Delta$ and girth $g$ whenever $q \ge \Delta+3$. Our approach is based on a new general reduction from spectral independence on large-girth graphs to SSM on trees that is of independent interest. Using the same techniques, we also prove near-optimal bounds on weak spatial mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts model on trees. Comment: 52 pages, 6 page appendix
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Mathematics - Combinatorics ; Mathematics - Probability
Subject code	511
Publishing date	2023-04-04
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Time Lower Bounds for the Metropolis Process and Simulated Annealing

Chen, Zongchen / Mikulincer, Dan / Reichman, Daniel / Wein, Alexander S.

2023

Abstract: The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality ...

Abstract	The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality of approximation obtained by MP and SA (with polynomially many iterations) for NP-hard optimization problems. We provide rigorous lower bounds for MP and SA with respect to the classical maximum independent set problem when the algorithms are initialized from the empty set. We establish the existence of a family of graphs for which both MP and SA fail to find approximate solutions in polynomial time. More specifically, we show that for any $\varepsilon \in (0,1)$ there are $n$-vertex graphs for which the probability SA (when limited to polynomially many iterations) will approximate the optimal solution within ratio $\Omega\left(\frac{1}{n^{1-\varepsilon}}\right)$ is exponentially small. Our lower bounds extend to graphs of constant average degree $d$, illustrating the failure of MP to achieve an approximation ratio of $\Omega\left(\frac{\log (d)}{d}\right)$ in polynomial time. In some cases, our impossibility results also go beyond Simulated Annealing and apply even when the temperature is chosen adaptively. Finally, we prove time lower bounds when the inputs to these algorithms are bipartite graphs, and even trees, which are known to admit polynomial-time algorithms for the independent set problem. Comment: 44 pages
Keywords	Computer Science - Data Structures and Algorithms ; Mathematics - Optimization and Control ; Mathematics - Probability
Subject code	511
Publishing date	2023-12-20
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Almost-Linear Planted Cliques Elude the Metropolis Process

Chen, Zongchen / Mossel, Elchanan / Zadik, Ilias

2022

Abstract: A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size $k=\Theta(n^{\alpha}), \alpha \in (0,1/2)$, which is planted in the Erd\H{ ... ...

Abstract	A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size $k=\Theta(n^{\alpha}), \alpha \in (0,1/2)$, which is planted in the Erd\H{o}s-R\'{e}nyi random graph $G(n,1/2)$, in polynomial time. Information theoretically it is possible to find such planted cliques as soon as $k \ge (2+\epsilon) \log n$. Since the work of Jerrum, the computational problem of finding a planted clique in $G(n,1/2)$ was studied extensively and many polynomial time algorithms were shown to find the planted clique if it is of size $k = \Omega(\sqrt{n})$, while no polynomial-time algorithm is known to work when $k=o(\sqrt{n})$. Notably, the first evidence of the problem's algorithmic hardness is commonly attributed to the result of Jerrum from 1992. In this paper we revisit the original Metropolis algorithm suggested by Jerrum. Interestingly, we find that the Metropolis algorithm actually fails to recover a planted clique of size $k=\Theta(n^{\alpha})$ for any constant $0 \leq \alpha < 1$. Moreover, we strengthen Jerrum's results in a number of other ways including: Like many results in the MCMC literature, the result of Jerrum shows that there exists a starting state (which may depend on the instance) for which the Metropolis algorithm fails. For a wide range of temperatures, we show that the algorithm fails when started at the most natural initial state, which is the empty clique. This answers an open problem stated in Jerrum (1992). We also show that the simulated tempering version of the Metropolis algorithm, a more sophisticated temperature-exchange variant of it, also fails at the same regime of parameters. Finally, our results confirm recent predictions by Gamarnik and Zadik (2019) and Angelini, Fachin, de Feo (2021).
Keywords	Computer Science - Data Structures and Algorithms ; Mathematics - Probability ; Mathematics - Statistics Theory
Subject code	511
Publishing date	2022-04-04
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: From algorithms to connectivity and back

Chen, Zongchen / Mani, Nitya / Moitra, Ankur

finding a giant component in random k-SAT

2022

Abstract: We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree $k$-CNFs for large $k$. In the course of doing so, we establish that with high probability, a random $k$-CNF $\Phi$ with $n$ variables ... ...

Abstract	We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree $k$-CNFs for large $k$. In the course of doing so, we establish that with high probability, a random $k$-CNF $\Phi$ with $n$ variables and clause density $\alpha = m/n \lesssim 2^{k/6}$ has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance $O_k(\log n)$ and that a similar result holds for bounded degree $k$-CNFs at similar densities. We are also able to deduce looseness results for random and bounded degree $k$-CNFs in a similar regime. Although our main motivation was understanding the geometry of the solution space, our methods have algorithmic implications. Towards that end, we construct an idealized block dynamics that samples solutions from a random $k$-CNF $\Phi$ with density $\alpha = m/n \lesssim 2^{k/52}$. We show this Markov chain can with high probability be implemented in polynomial time and by leveraging spectral independence, we also observe that it mixes relatively fast, giving a polynomial time algorithm to with high probability sample a uniformly random solution to a random $k$-CNF. Our work suggests that the natural route to pinning down when a giant component exists is to develop sharper algorithms for sampling solutions in random $k$-CNFs. Comment: 41 pages, 1 figure
Keywords	Computer Science - Data Structures and Algorithms ; 68W20 ; 68W25 ; 68W40 ; 68Q87 ; G.3 ; F.2.2
Subject code	519
Publishing date	2022-07-06
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Identity Testing for High-Dimensional Distributions via Entropy Tensorization

Blanca, Antonio / Chen, Zongchen / Štefankovič, Daniel / Vigoda, Eric

2022

Abstract: We present improved algorithms and matching statistical and computational lower bounds for the problem of identity testing $n$-dimensional distributions. In the identity testing problem, we are given as input an explicit distribution $\mu$, an $\ ... ...

Abstract	We present improved algorithms and matching statistical and computational lower bounds for the problem of identity testing $n$-dimensional distributions. In the identity testing problem, we are given as input an explicit distribution $\mu$, an $\varepsilon>0$, and access to a sampling oracle for a hidden distribution $\pi$. The goal is to distinguish whether the two distributions $\mu$ and $\pi$ are identical or are at least $\varepsilon$-far apart. When there is only access to full samples from the hidden distribution $\pi$, it is known that exponentially many samples may be needed, and hence previous works have studied identity testing with additional access to various conditional sampling oracles. We consider here a significantly weaker conditional sampling oracle, called the Coordinate Oracle, and provide a fairly complete computational and statistical characterization of the identity testing problem in this new model. We prove that if an analytic property known as approximate tensorization of entropy holds for the visible distribution $\mu$, then there is an efficient identity testing algorithm for any hidden $\pi$ that uses $\tilde{O}(n/\varepsilon)$ queries to the Coordinate Oracle. Approximate tensorization of entropy is a classical tool for proving optimal mixing time bounds of Markov chains for high-dimensional distributions, and recently has been established for many families of distributions via spectral independence. We complement our algorithmic result for identity testing with a matching $\Omega(n/\varepsilon)$ statistical lower bound for the number of queries under the Coordinate Oracle. We also prove a computational phase transition: for sparse antiferromagnetic Ising models over $\{+1,-1\}^n$, in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless RP=NP.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Machine Learning ; Mathematics - Probability ; Mathematics - Statistics Theory
Subject code	519
Publishing date	2022-07-19
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Article: Visible light-regulated BiVO4-based micromotor with biomimetic ‘predator-bait’ behavior

Chen, Zongchen / Jiang, Jiwei / Wang, Xin / Zhang, Hui / Song, Bo / Dong, Bin

Journal of materials science. 2022 Feb., v. 57, no. 6

2022

Abstract: Inspired by the swarming behavior of various bacteria in nature, light-driven micromotor with collective behavior has attracted a great deal of attention, which will be a valuable tool to understand the cooperation and communication between bacterial ... ...

Abstract	Inspired by the swarming behavior of various bacteria in nature, light-driven micromotor with collective behavior has attracted a great deal of attention, which will be a valuable tool to understand the cooperation and communication between bacterial populations and will contribute to the creation of reconfigurable microrobots and the cooperative transportation of large cargoes. However, it is still challenging to modulate the micromotors’ collective behavior based on local interaction and communication. Herein, we develop a light-powered BiVO₄-based micromotor with self-propulsion and dynamic ‘predator-bait’ collective behavior, which is based on the photocatalytic reaction of BiVO₄. The BiVO₄-based micromotor has great potential in the field of organic pollutant degradation with enhanced apparent rate constant (0.076 min⁻¹) which originates from the dynamic ‘predator-bait’ behavior.
Keywords	biomimetics ; group behavior ; photocatalysis ; pollutants ; transportation
Language	English
Dates of publication	2022-02
Size	p. 4092-4103.
Publishing place	Springer US
Document type	Article
ZDB-ID	2015305-3
ISSN	1573-4803 ; 0022-2461
ISSN (online)	1573-4803
ISSN	0022-2461
DOI	10.1007/s10853-022-06882-w
Database	NAL-Catalogue (AGRICOLA)

Full text online

Accessible to users with ZB MED library card

Order via subito

This service is chargeable due to the Delivery terms set by subito. Orders including an article and supplementary material will be classified as separate orders. In these cases, fees will be demanded for each order.

Details ▾
- Full text online
- Order with fees

Book ; Online: Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region

Chen, Zongchen / Galanis, Andreas / Štefankovič, Daniel / Vigoda, Eric

2021

Abstract: For spin systems, such as the $q$-colorings and independent-set models, approximating the partition function in the so-called non-uniqueness region, where the model exhibits long-range correlations, is typically computationally hard for bounded-degree ... ...

Abstract	For spin systems, such as the $q$-colorings and independent-set models, approximating the partition function in the so-called non-uniqueness region, where the model exhibits long-range correlations, is typically computationally hard for bounded-degree graphs. We present new algorithmic results for approximating the partition function and sampling from the Gibbs distribution for spin systems in the non-uniqueness region on random regular bipartite graphs. We give an $\mathsf{FPRAS}$ for counting $q$-colorings for even $q=O\big(\tfrac{\Delta}{\log{\Delta}}\big)$ on almost every $\Delta$-regular bipartite graph. This is within a factor $O(\log{\Delta})$ of the sampling algorithm for general graphs in the uniqueness region and improves significantly upon the previous best bound of $q=O\big(\tfrac{\sqrt{\Delta}}{(\log\Delta)^2}\big)$ by Jenssen, Keevash, and Perkins (SODA'19). Analogously, for the hard-core model on independent sets weighted by $\lambda>0$, we present an $\mathsf{FPRAS}$ for estimating the partition function when $\lambda=\Omega\big(\tfrac{\log{\Delta}}{\Delta}\big)$, which improves upon previous results by an $\Omega(\log \Delta)$ factor. Our results for the colorings and hard-core models follow from a general result that applies to arbitrary spin systems. Our main contribution is to show how to elevate probabilistic/analytic bounds on the marginal probabilities for the typical structure of phases on random bipartite regular graphs into efficient algorithms, using the polymer method. We further show evidence that our result for colorings is within a constant factor of best possible using current polymer-method approaches.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Mathematics - Combinatorics ; Mathematics - Probability
Subject code	005
Publishing date	2021-05-04
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top

Your last searches

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Order via subito

Full text online

More links

Kategorien

Inter-library loan at ZB MED