Yiyao Zhang

I am a third-year Ph.D. student in Computer Science at Nanjing University and a member of the Theory Group, advised by Prof. Yitong Yin. I earned my B.S. in Computer Science from Nanjing University in 2024.

Research Interests: Sampling and Counting; Learning Theory; Probability Theory

Education

Nanjing University

Ph.D. in Computer Science

Advisor: Prof. Yitong Yin

Nanjing University

B.S. in Computer Science

Publications

Authors are listed alphabetically unless otherwise stated.

Preprints

  1. Single-Variable Connectivity in Random k-SAT.

    Abstract

    We resolve longstanding questions about connectivity, reconstruction, and looseness in random k-SAT, for sufficiently large fixed k as the number n of variables tends to infinity.

    Single-variable connectivity up to reconstruction. At clause densities up to

    \frac{2^{k}}{k}\bigl(\ln k+\ln\ln k+\gamma_{*}-o_{k}(1)\bigr),

    a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using O_{k}(n) single-variable flips that preserve satisfiability. Here \gamma_{*}\approx 0.871 arises from a refined tree-reconstruction analysis.

    Settling the reconstruction threshold. Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be

    \frac{2^{k}}{k}\bigl(\ln k+\ln\ln k+\gamma_{*}+o_{k}(1)\bigr),

    below the classical cavity prediction with constant term 1+O(\ln\ln k/\ln k).

    Shattering before rigidity. We locate the looseness–rigidity transition at a higher density, matching the classical cavity prediction for clustering:

    \frac{2^{k}}{k}\left(\ln k+\ln\ln k+1+\Theta\left(\frac{\ln\ln k}{\ln k}\right)\right).

    Below the transition, we establish a stronger form of looseness: any variable of a typical solution can be reversed by logarithmically many single-variable flips that preserve satisfiability. Above it, reversing most variables of a typical solution requires changing linearly many variables (rigidity). Yet throughout an interval between reconstruction and rigidity, the solution space already splits into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers (shattering), while logarithmic looseness persists.

    These results resolve the giant-component and logarithmic-looseness conjectures of Chen–Mani–Moitra (SODA 2023), the sublinear-looseness conjecture of Achlioptas–Coja-Oghlan (FOCS 2008), and the reconstruction formulation of the clustering problem of Krzakala–Montanari–Ricci-Tersenghi–Semerjian–Zdeborová (PNAS 2007).

    Chunyang Wang, Yitong Yin, Yixiao Yu, Yiyao Zhang.

    arXiv: 2611.05981. arXiv

  2. An Õ(n2)-Time Sampler for Zero-Field Ferromagnetic Ising Models.

    Abstract

    We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time \widetilde{O}(m+n)+\widetilde{O}_{\beta}(n^{2}\log^{2}(1/\varepsilon)), where n and m are the numbers of vertices and edges, respectively, and \varepsilon is the approximation error. Our approach combines Benczúr–Karger cut sparsification with a new mixing time analysis of the Glauber dynamics for the random-cluster model. The mixing time analysis features a new monotone edge-count Poincaré inequality.

    Weiming Feng, Heng Guo, Yiyao Zhang.

    arXiv: 2609.26197. arXiv

  3. Optimal Simulated Annealing for Partition Function Estimation.

    Abstract

    In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most efficient reduction of this kind so far. We also establish lower bounds for both general and non-adaptive algorithms, showing that our algorithm is optimal over a broad range of parameters.

    Heng Guo, Hongyang Liu, Xiongxin Yang, Yitong Yin, Yiyao Zhang.

    arXiv: 2609.20337. arXiv

  4. Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm.

    Abstract

    We revisit Valiant’s algorithm (Commun. ACM’84) for learning n-variable CNF formulas with clause size k and variable degree d from i.i.d. uniform random solutions in the local lemma regime. For fixed t\geq 1, under k\gtrsim(1+1/t)\log d, Valiant’s algorithm achieves total variation error \varepsilon with \widetilde{O}(n^{\left\lceil t\right\rceil}/\varepsilon) sample complexity. For t>1, we prove a matching lower bound for Valiant’s algorithm. At t=1 (covering 0<t<1), we show Valiant’s algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound \widetilde{\Omega}(n/\varepsilon).

    Weiming Feng, Yixiao Yu, Yiyao Zhang.

    arXiv: 2609.15268. arXiv

  5. A Counting and Sampling Lovász Local Lemma.

    Abstract

    We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime

    4\mathrm{e}p(D+1)^{2}\leq 1,

    where p is the maximum constraint violation probability and D is the maximum dependency degree.

    This condition is tight up to constant factors under \mathbf{NP}\neq\mathbf{RP}, matching known hardness bounds for counting and sampling in natural subclasses of CSPs. Our key ingredient is a novel 2-tree expansion for constraint marginal probabilities that exhibits exponential decay of correlations throughout this regime.

    This expansion yields deterministic polynomial-time approximate counting for fixed local parameters, randomized approximate counting with quadratic cost, and exact sampling in expected near-linear time when the local parameters are fixed.

    Hongyang Liu, Chunyang Wang, Yitong Yin, Yiyao Zhang, Can Zhou.

    arXiv: 2608.08616. arXiv

Conference Papers

  1. Learning AC0 under Locally Sampleable Graphical Models.

    Abstract

    The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for \mathsf{AC}^{0} under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth.

    In this paper, we give a quasipolynomial-time learner for \mathsf{AC}^{0} under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.

    Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang.

    SODA 2027, To appear. arXiv

  2. Near-Optimal Parallel Approximate Counting via Sampling.

    Abstract

    The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is based on simulated annealing. In this approach, the counting problem is formulated as estimating the ratio Q={Z(\beta_{\max})}/{Z(\beta_{\min})} between partition functions Z(\beta)=\sum_{x\in\Omega}\exp(\beta H(x)) of Gibbs distributions \mu_{\beta} over \Omega with Hamiltonian H, given access to a sampling oracle for \mu_{\beta} at any \beta\in[\beta_{\min},\beta_{\max}]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound \ln Q and H. The best upper bound achieved by known annealing algorithms with relative error \varepsilon is O(q\varepsilon^{-2}\log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters \beta depend on previous samples.

    We develop a simple non-adaptive algorithm for approximate counting using O(q\varepsilon^{-2}\log^{2}h) samples, as well as an algorithm that achieves O(q\varepsilon^{-2}\log h) samples with just two additional adaptive rounds, matching the best sample complexity of sequential algorithms. These algorithms naturally yield work-efficient parallel (RNC) counting algorithms. We discuss applications to several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.

    David G. Harris, Vladimir Kolmogorov, Hongyang Liu, Yitong Yin, Yiyao Zhang.

    SPAA 2026, pp. 550-559. Slides@SPAA Conference Version arXiv

  3. Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime.

    Abstract

    We study the problem of learning a n-variables k-CNF formula \Phi from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with k-wise hard constraints. Revisiting Valiant’s algorithm (Commun. ACM’84), we show that it can exactly learn (1) k-CNFs with bounded clause intersection size under Lovász local lemma type conditions, from O(\log n) samples; and (2) random k-CNFs near the satisfiability threshold, from \widetilde{O}(n^{\exp(-\sqrt{k})}) samples. These results significantly improve the previous O(n^{k}) sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from i.i.d. uniform random solutions.

    Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang.

    STOC 2026, pp. 478-488. Poster by Xiongxin Slides@STOC Conference Version arXiv

  4. Hyper-USS: Answering Subset Query over Multi-Attribute Data Stream.

    Abstract

    Sketching algorithms are considered as promising solutions for answering approximate query on massive data stream. In real scenarios, a large number of problems can be abstracted as subset query over multiple attributes. Existing sketches are designed for query on single attributes, and therefore are inefficient for query on multiple attributes. In this work, we propose Hyper-USS, an innovative sketching algorithm that supports subset query over multiple attributes accurately and efficiently. To the best of our knowledge, this work is the first sketching algorithm designed to answer approximate query over multi-attribute data stream. We utilize the key technique, Joint Variance Optimization, to guarantee high estimation accuracy on all attributes. Experiment results show that, compared with the state-of-the-art (SOTA) sketches that support subset query on single attributes, Hyper-USS improves the accuracy by 16.67× and the throughput by 8.54×. The code is open-sourced at Github.

    Ruijie Miao, Yiyao Zhang, Guanyu Qu, Kaicheng Yang, Tong Yang, Bin Cui. (by contribution)

    SIGKDD 2023, pp. 1698-1709. Conference Version

Talks

  1. Near-Optimal Parallel Approximate Counting via Sampling.

    SPAA 2026, London, UK.

  2. Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime.

    STOC 2026, Salt Lake City, USA.

Visiting and Internship

The University of Hong Kong

Research assistant hosted by Asst. Prof. Weiming Feng.

Teaching Assistantship

Advanced Algorithms (Nanjing University)

Instructors: Yitong Yin, Shi Li, Jingcheng Liu.

Awards