4 citations · 6 across the 13 of their papers we have counts for
16 papers
Subgaussian Vector Balancing by an Ising Model
Heng Guo, Daniel A. Spielman, Xinyuan Zhang
We show that the guaranties of the Gram-Schmidt Walk Algorithm of Bansal, Dadush, Garg, and Lovett can be achieved by an Ising model. Given vectors of norm less…
Simulating Gaussian boson sampling on graphs in polynomial time
Konrad Anand, Zongchen Chen, Mary Cryan +4
We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS typically sample from th…
Blocklisted Oblivious Pseudorandom Functions
Xinyuan Zhang, Anrin Chakraborti, Michael Reiter
An oblivious pseudorandom function (OPRF) is a protocol by which a client and server interact to evaluate a pseudorandom function on a key provided by the server and an input provi…
Efficient Parallel Ising Samplers via Localization Schemes
Xiaoyu Chen, Hongyang Liu, Yitong Yin +1
We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficie…
Faster Mixing of the Jerrum-Sinclair Chain
Xiaoyu Chen, Weiming Feng, Zhe Ju +3
We show that the Jerrum-Sinclair Markov chain on matchings mixes in time on any graph with vertices, edges, and maximum degree , for any constant…
Rapid Mixing on Random Regular Graphs beyond Uniqueness
Xiaoyu Chen, Zejia Chen, Zongchen Chen +2
The hardcore model is a fundamental probabilistic model extensively studied in statistical physics, probability theory, and computer science. For graphs of maximum degree , a we…
Rapid Mixing at the Uniqueness Threshold
Xiaoyu Chen, Zongchen Chen, Yitong Yin +1
Over the past decades, a fascinating computational phase transition has been identified in sampling from Gibbs distributions. Though, the computational complexity at the critical p…
Deterministic counting from coupling independence
Xiaoyu Chen, Weiming Feng, Heng Guo +2
We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting…
MapComp: A Secure View-based Collaborative Analytics Framework for Join-Group-Aggregation
Xinyu Peng, Feng Han, Li Peng +8
Join-group-aggregation (JGA) queries are fundamental to data analytics, yet executing them collaboratively across different parties poses significant privacy risks. Secure multi-pa…
Spectral Independence Beyond Total Influence on Trees and Related Graphs
Xiaoyu Chen, Xiongxin Yang, Yitong Yin +1
We study how to establish , a key concept in sampling, without relying on total influence bounds, by applying an of t…
A Near-Linear Time Sampler for the Ising Model with External Field
Xiaoyu Chen, Xinyuan Zhang
We give a near-linear time sampler for the Gibbs distribution of the ferromagnetic Ising models with edge activities and external fields (or sym…
Optimal mixing for two-state anti-ferromagnetic spin systems
Xiaoyu Chen, Weiming Feng, Yitong Yin +1
We prove an optimal lower bound for modified log-Sobolev (MLS) constant of the Glauber dynamics for anti-ferromagnetic two-spin systems with vertices in the tree un…
Polynomial-Time Approximation of Zero-Free Partition Functions
Penghui Yao, Yitong Yin, Xinyuan Zhang
Zero-free based algorithm is a major technique for deterministic approximate counting. In Barvinok's original framework[Bar17], by calculating truncated Taylor expansions, a quasi-…
Optimal Mixing Time for the Ising Model in the Uniqueness Regime
Xiaoyu Chen, Weiming Feng, Yitong Yin +1
We prove an optimal mixing time of the Glauber dynamics for the Ising models with edge activity . This mixing time bound h…
Rapid mixing of Glauber dynamics via spectral independence for all degrees
Xiaoyu Chen, Weiming Feng, Yitong Yin +1
We prove an optimal lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with vertices in the tree uniqueness regime. This sp…
Mixing Strategies in Cryptocurrencies and An Alternative Implementation
Xinyuan Zhang
Since the initial launch of Bitcoin by Satoshi Nakamoto in 2009, decentralized digital currencies have long been of major interest in both the academia and the industry. Till today…