18 citations · 27 across the 12 of their papers we have counts for
Showing 2022 · cs.DSShow all
3 papers · 2 filters
cs.DS2022
From algorithms to connectivity and back: finding a giant component in random k-SAT
Zongchen Chen, Nitya Mani, Ankur Moitra
We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree -CNFs for large . In the course of doing so, we establi…
cs.DS2022
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution , an , and access to sampling oracle(s) for a hi…
cs.DS2022
Almost-Linear Planted Cliques Elude the Metropolis Process
Zongchen Chen, Elchanan Mossel, Ilias Zadik
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…