35 citations · 194 across the 35 of their papers we have counts for
14 papers · 1 filter
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…
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…
Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
Jingcheng Liu, Yixiao Yu
We show that for -colorings in -uniform hypergraphs with maximum degree , if and , there is a "Lee-Yang" zero-free strip around the i…
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…
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…
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} -vertex, -edge graph with a \emph{maximum unweighted} degree $Δ(G) \leq n…
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…
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…
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…
The Ising Partition Function: Zeros and Deterministic Approximation
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (a…
Uniform Sampling through the Lovász Local Lemma
Heng Guo, Mark Jerrum, Jingcheng Liu
We propose a new algorithmic framework, called "partial rejection sampling", to draw samples exactly from a product distribution, conditioned on none of a number of bad events occu…
FPTAS for #BIS with Degree Bounds on One Side
Jingcheng Liu, Pinyan Lu
Counting the number of independent sets for a bipartite graph (#BIS) plays a crucial role in the study of approximate counting. It has been conjectured that there is no fully polyn…
FPTAS for Counting Monotone CNF
Jingcheng Liu, Pinyan Lu
A monotone CNF formula is a Boolean formula in conjunctive normal form where each variable appears positively. We design a deterministic fully polynomial-time approximation scheme…
A Simple FPTAS for Counting Edge Covers
Chengyu Lin, Jingcheng Liu, Pinyan Lu
An edge cover of a graph is a set of edges such that every vertex has at least an adjacent edge in it. Previously, approximation algorithm for counting edge covers is only known fo…