Jingcheng Liu

activity

20132026

most citedSpectral property of self-affine measures on

R^{n}

35 citations · 194 across the 35 of their papers we have counts for

collaborators

35 papers

cs.DS2026

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

Chenglin Fan, Jingcheng Liu, Pan Peng +2

We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additi…

math.ST2026

Recovery thresholds for hidden weighted sparse graphs

Zhe Hou, Jingcheng Liu

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the recovery thresholds for a graph hidden in a ra…

math.FA2026

Spectrality of product-form self-similar measures and tiles

Jing-Cheng Liu, Jia-Jie Wang, Jia Zheng

This paper studies the Fourier properties of self-similar measures and tiles generated by digit sets of product-form. Let $0 < ρ < 1$ be a real number and let $D$ be the direct sum of…

cs.DS2026

The Price of Privacy For Approximating Max-CSP

Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi +3

We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Infor…

cs.DS2026

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime

Jingcheng Liu, Yixiao Yu

We show that for $q$ -colorings in $k$ -uniform hypergraphs with maximum degree $Δ$ , if $k \geq 50$ and $q \geq 700 Δ^{\frac{5}{k - 10}}$ , there is a "Lee-Yang" zero-free strip around the i…

math.FA2025

A class of spectral measures with $m$ -alternate contraction ratios in $R$

Jing-cheng Liu, Jia-jie Wang

For a Borel probability measure $μ$ on $R^{n}$ , it is called a spectral measure if the Hilbert space $L^{2} (μ)$ admits an orthogonal basis of exponential functions. In thi…

quant-ph2025

Optimal quantum sampling on distributed databases

Longyun Chen, Jingcheng Liu, Penghui Yao

Quantum sampling, a fundamental subroutine in numerous quantum algorithms, involves encoding a given probability distribution in the amplitudes of a pure state. Given the hefty cos…

cs.DS2025

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances

Michael Dinitz, Chenglin Fan, Jingcheng Liu +2

We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected…

cs.DS2025

Phase Transitions via Complex Extensions of Markov Chains

Jingcheng Liu, Chunyang Wang, Yitong Yin +1

We study algebraic properties of partition functions, particularly the location of zeros, through the lens of rapidly mixing Markov chains. The classical Lee-Yang program initiated…

math.FA2024

Spectrality of alternating-sign Moran measures

Jun Jason Luo, Lin Mao, Jing-Cheng Liu

For $m\geq 2$, let $D_m=\{0,1,\ldots,m-1\}$. For each $k\geq 1$, consider the family of contractions \[ Φ_k=\{ϕ_{k,d}:d\in D_{n_k}\}, \qquad ϕ_{k,d}(x)=(-1)^d b_k^{-1}(x+d),…

math.FA2024

Spectrality of a class of moran measures on $R^{2}$

Jing-Cheng Liu, Qiao-Qin Liu, Jun Jason Luo +1

We investigate spectral properties of planar Moran measures $μ_{{M_{n}}, {D_{n}}}$ generated by sequences of expanding matrices ${M_{n}} \subset G L (2, Z)$ and digit sets $\{D…

cs.CC2024

Perfect sampling from rapidly mixing Markov chains

Andreas Göbel, Jingcheng Liu, Pasin Manurangsi +1

We show that efficient approximate sampling algorithms, combined with a slow exponential time oracle for computing its output distribution, can be combined into constructing effici…

cs.CR2024

Almost linear time differentially private release of synthetic graphs

Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou

In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $ℓ_{1}$ -score function defined over an exponentially large non-co…

cs.CR2024★ 1 cited

Optimality of Matrix Mechanism on $ℓ_{p}^{p}$ -metric

Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou

In this paper, we introduce the $ℓ_{p}^{p}$ -error metric (for $p \geq 2$ ) when answering linear queries under the constraint of differential privacy. We characterize such an error u…

cs.DS2023

Optimal Bounds on Private Graph Approximation

Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou

We propose an efficient $ε$ -differentially private algorithm, that given a simple {\em weighted} $n$ -vertex, $m$ -edge graph $G$ with a \emph{maximum unweighted} degree $Δ(G) \leq n…

cs.DS2023★ 1 cited

Uniqueness and Rapid Mixing in the Bipartite Hardcore Model

Xiaoyu Chen, Jingcheng Liu, Yitong Yin

We characterize the uniqueness condition in the hardcore model for bipartite graphs with degree bounds only on one side, and provide a nearly linear time sampling algorithm that wo…

math.FA2022

Fourier bases of a class of planar self-affine measures

Ming-Liang Chen, Jing-Cheng Liu, Zhi-Yong Wang

Let $μ_{M, D}$ be the planar self-affine measure generated by an expansive integer matrix $M \in M_{2} (Z)$ and a non-collinear integer digit set $D=\left\{\begin{pmatrix} 0\\0…

math.CA2020

Spectrality of generalized Sierpinski-type self-affine measures

Jing-Cheng Liu, Ying Zhang, Zhi-Yong Wang +1

For an expanding integer matrix $M \in M_{2} (Z)$ and an integer digit set $D = {(0, 0)^{t}, (α_{1}, α_{2})^{t}, (β_{1}, β_{2})^{t}}$ with $α_{1} β_{2} - α_{2} β_{1} \neq = 0$ , let $μ_{M, D}$ be the Sierpinski-t…

math.FA2020★ 2 cited

The spectrality of self-affine measure under the similarity transformation of $G L_{n} (p)$

Jing-Cheng Liu, Zhi-Yong Wang

Let $μ_{M, D}$ be the self-affine measure generated by an expanding integer matrix $M \in M_{n} (Z)$ and a finite digit set $D \subset Z^{n}$ . It is well known that the tw…

cs.DS2019★ 1 cited

Zeros of ferromagnetic 2-spin systems

Heng Guo, Jingcheng Liu, Pinyan Lu

We study zeros of the partition functions of ferromagnetic 2-state spin systems in terms of the external field, and obtain new zero-free regions of these systems via a refinement o…

cs.CC2019★ 12 cited

Correlation decay and partition function zeros: Algorithms and phase transitions

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

We explore connections between the phenomenon of correlation decay and the location of Lee-Yang and Fisher zeros for various spin systems. In particular we show that, in many insta…

cs.DS2018★ 3 cited

Private Selection from Private Candidates

Jingcheng Liu, Kunal Talwar

Differentially Private algorithms often need to select the best amongst many candidate options. Classical works on this selection problem require that the candidates' goodness, mea…

math-ph2018★ 30 cited

Fisher zeros and correlation decay in the Ising model

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

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 in…

math.FA2018★ 1 cited

The cardinality of orthogonal exponentials of planar self-affine measures with three-element digit sets

Ming-Liang Chen, Jing-Cheng Liu

In this paper, we consider the planar self-affine measures $μ_{M, D}$ generated by an expanding matrix $M \in M_{2} (Z)$ and an integer digit set $ D=\left\{ {\left( {\begin{ar…

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

Recovery thresholds for hidden weighted sparse graphs

Spectrality of product-form self-similar measures and tiles

The Price of Privacy For Approximating Max-CSP

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime

A class of spectral measures with m-alternate contraction ratios in R

Optimal quantum sampling on distributed databases

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances

Phase Transitions via Complex Extensions of Markov Chains

Spectrality of alternating-sign Moran measures

Spectrality of a class of moran measures on R2

Perfect sampling from rapidly mixing Markov chains

Almost linear time differentially private release of synthetic graphs

Optimality of Matrix Mechanism on ℓpp​-metric

Optimal Bounds on Private Graph Approximation

Uniqueness and Rapid Mixing in the Bipartite Hardcore Model

Fourier bases of a class of planar self-affine measures

Spectrality of generalized Sierpinski-type self-affine measures

The spectrality of self-affine measure under the similarity transformation of GLn​(p)

Zeros of ferromagnetic 2-spin systems

Correlation decay and partition function zeros: Algorithms and phase transitions

Private Selection from Private Candidates

Fisher zeros and correlation decay in the Ising model

The cardinality of orthogonal exponentials of planar self-affine measures with three-element digit sets

A class of spectral measures with $m$ -alternate contraction ratios in $R$

Spectrality of a class of moran measures on $R^{2}$

Optimality of Matrix Mechanism on $ℓ_{p}^{p}$ -metric

The spectrality of self-affine measure under the similarity transformation of $G L_{n} (p)$