Author name cluster

Jiapeng Zhang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers

2 author rows

AAAI Conference 2026 Conference Paper

LiNeXt: Revisiting LiDAR Completion with Efficient Non-Diffusion Architectures

Wenzhe He
Xiaojun Chen
Ruiqi Wang
Ruihui Li
Huilong Pi
Jiapeng Zhang
Zhuo Tang
Kenli Li

3D LiDAR scene completion from point clouds is a fundamental component of perception systems in autonomous vehicles. Previous methods have predominantly employed diffusion models for high‑fidelity reconstruction. However, their multi-step iterative sampling incurs significant computational overhead, limiting its real-time applicability. To address this, we propose LiNeXt: a lightweight, non‐diffusion network optimized for rapid and accurate point cloud completion. Specifically, LiNeXt first applies the Noise‑to‑Coarse (N2C) Module to denoise the input noisy point cloud in a single pass, thereby obviating the multi‑step iterative sampling of diffusion‑based methods. The Refine Module then takes the coarse point cloud and its intermediate features from the N2C Module to perform more precise refinement, further enhancing structural completeness. Furthermore, we observe that LiDAR point clouds exhibit a distance-dependent spatial distribution, being densely sampled at proximal ranges and sparsely sampled at distal ranges. Accordingly, we propose the Distance‑aware Selected Repeat strategy to generate a more uniformly distributed noisy point cloud. On the SemanticKITTI dataset, LiNeXt achieves a 199.8 times speedup in inference, reduces Chamfer Distance by 50.7 percent, and uses only 6.1 percent of the parameters compared with LiDiff. These results demonstrate the superior efficiency and effectiveness of LiNeXt for real-time scene completion.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Self-Indexing KVCache: Predicting Sparse Attention from Compressed Keys

Xu Yang
Jiapeng Zhang
Dongyang Zhao
Guo Chen
Zhuo Tang

The KV cache in self-attention has emerged as a major bottleneck in long-context and large-batch inference for LLMs. Existing approaches often treat sparsity prediction and compression as separate modules—relying on auxiliary index structures to select relevant tokens, and on complex quantization schemes to reduce memory usage. This fragmented design introduces redundant overhead and limits scalability. In this paper, we propose a novel paradigm: treating the compressed key representation not merely as storage, but as a self-indexing structure that directly enables efficient sparse attention. By designing a sign-based 1-bit vector quantization (VQ) scheme, our method unifies compression and retrieval in a single, hardware-friendly format. This approach eliminates the need for external indices or learning-based predictors, offering a lightweight yet robust solution for memory-constrained inference. All components are designed to be hardware-efficient and easy to implement. By implementing custom CUDA kernels, our method integrates seamlessly with FlashAttention, minimizing additional runtime and memory overhead. Experimental results demonstrate that our approach delivers both effectiveness and efficiency.

PDF Details DOI

ICLR Conference 2025 Conference Paper

Balanced Ranking with Relative Centrality: A multi-core periphery perspective

Chandra Sekhar Mukherjee
Jiapeng Zhang

Ranking of vertices in a graph for different objectives is one of the most fundamental tasks in computer science. It is known that traditional ranking algorithms can generate unbalanced ranking when the graph has underlying communities, resulting in loss of information, polarised opinions, and reduced diversity (Celis, Straszak \& Vishnoi [ICALP 2018]). In this paper, we focus on *unsupervised ranking* on graphs and observe that popular centrality measure based ranking algorithms such as PageRank may often generate unbalanced ranking here as well. We address this issue by coining a new approach, which we term *relative centrality*. Our approach is based on an iterative graph-dependent local normalization of the centrality score, which promotes balancedness while maintaining the validity of the ranking. We further quantify reasons behind this unbalancedness of centrality measures on a novel structure that we propose is called multi-core-periphery with communities (MCPC). We also provide theoretical and extensive simulation support for our approach towards resolving the unbalancedness in MCPC. Finally, we consider graph embeddings of $11$ single-cell datasets. We observe that top-ranked as per existing centrality measures are better separable into the ground truth communities. However, due to the unbalanced ranking, the top nodes often do not contain points from some communities. Here, our relative-centrality-based approach generates a ranking that provides a similar improvement in clusterability while providing significantly higher balancedness.

Details

IJCAI Conference 2025 Conference Paper

TOTF: Missing-Aware Encoders for Clustering on Multi-View Incomplete Attributed Graphs

Mengyao Li
Xu Zhou
Jiapeng Zhang
Zhibang Yang
Cen Chen
Kenli Li

As the network data in real life become multi-modal and multi-relational, multi-view attributed graphs have garnered significant attention. Numerous methods have achieved excellent performance in multi-view attributed graph clustering; however, they cannot efficiently handle incomplete attribute scenarios, which are prevalent in many real-life applications. Inspired by this, we investigate the problem of multi-view incomplete attributed graph clustering for the first time. In particular, the TOTF (Train Once Then Freeze) framework is designed to train missing-aware encoders that capture view-specific information while ignoring the impact of incomplete attributes, and then employs frozen encoders to uncover common information driven by clustering. After that, we propose a correlation strength-aware graph neural network on the basis of the inherent relationships among attributes to enhance accuracy. It is proven theoretically that traditional Generative Adversarial Networks (GANs) are unable to generate the unique real distribution. To address this issue, we further introduce the missing-position reminder mechanism into our intra-view adversarial games for better clustering results. Extensive experimental results demonstrate that our method achieves up to a 17% improvement in accuracy over the state-of-the-art methods. The source code is available at https: //anonymous. 4open. science/r/TOTF-main.

PDF Details DOI

STOC Conference 2024 Conference Paper

A New Information Complexity Measure for Multi-pass Streaming with Applications

Mark Braverman
Sumegha Garg
Qian Li 0012
Shuo Wang
David P. Woodruff
Jiapeng Zhang

We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one sees a stream of n i.i.d. uniformly random bits and one would like to compute the majority with constant advantage. We show that any constant-pass algorithm must use Ω(log n ) bits of memory, significantly extending an earlier Ω(log n ) bit lower bound for single-pass algorithms of Braverman-Garg-Woodruff (FOCS, 2020). This also gives the first Ω(log n ) bit lower bound for the problem of approximating a counter up to a constant factor in worst-case turnstile streams for more than one pass. In the needle problem, one either sees a stream of n i.i.d. uniform samples from a domain [ t ], or there is a randomly chosen needle α ∈[ t ] for which each item independently is chosen to equal α with probability p , and is otherwise uniformly random in [ t ]. The problem of distinguishing these two cases is central to understanding the space complexity of the frequency moment estimation problem in random order streams. We show tight multi-pass space bounds for this problem for every p < 1/√ n log 3 n , resolving an open question of Lovett and Zhang (FOCS, 2023); even for 1-pass our bounds are new. To show optimality, we improve both lower and upper bounds from existing results. Our information complexity framework significantly extends the toolkit for proving multi-pass streaming lower bounds, and we give a wide number of additional streaming applications of our lower bound techniques, including multi-pass lower bounds for ℓ p -norm estimation, ℓ p -point query and heavy hitters, and compressed sensing problems.

Details

NeurIPS Conference 2024 Conference Paper

Capturing the denoising effect of PCA via compression ratio

Chandra Sekhar Mukherjee
Nikhil Deorkar
Jiapeng Zhang

Principal component analysis (PCA) is one of the most fundamental tools in machine learning with broad use as a dimensionality reduction and denoising tool. In the later setting, while PCA is known to be effective at subspace recovery and is proven to aid clustering algorithms in some specific settings, its improvement of noisy data is still not well quantified in general. In this paper, we propose a novel metric called compression ratio to capture the effect of PCA on high-dimensional noisy data. We show that, for data with underlying community structure, PCA significantly reduces the distance of data points belonging to the same community while reducing inter-community distance relatively mildly. We explain this phenomenon through both theoretical proofs and experiments on real-world data. Building on this new metric, we design a straightforward algorithm that could be used to detect outliers. Roughly speaking, we argue that points that have a lower variance of compression ratio do not share a common signal with others (hence could be considered outliers). We provide theoretical justification for this simple outlier detection algorithm and use simulations to demonstrate that our method is competitive with popular outlier detection tools. Finally, we run experiments on real-world high-dimension noisy data (single-cell RNA-seq) to show that removing points from these datasets via our outlier detection method improves the accuracy of clustering algorithms. Our method is very competitive with popular outlier detection tools in this task.

PDF Details DOI

STOC Conference 2024 Conference Paper

Communication Lower Bounds for Collision Problems via Density Increment Arguments

Guangxu Yang
Jiapeng Zhang

Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), G'o'os and Jain (RANDOM 2022) independently proposed the communication version of collision problems. In the communication setting, both Alice and Bob receive k random subsets of [ N ]: S 1 ,…, S k and T 1 ,…, T k with each of size roughly √ N , where a typical choice of k is in the order of √ N for applications. Then Alice and Bob aim to find a pair ( x , x ′) such that x , x ′∈ S i ∩ T j for some S i and T j . A simple protocol that solves this problem with O ( N 1/4 ) communication bits is the following: Alice sends to Bob a random subset of S 1 of size N 1/4 and Bob checks if there is a set T j that has more than two intersections to this subset. All the papers mentioned above believe this bound should be tight up to some log factors. In this paper, we prove an Ω( N 1/4 ) randomized communication lower bound, affirming the conjecture above. Previously, only an Ω( N 1/12 ) was known by a work of G'o'os and Jain (RANDOM 2022). Our lower bound provides direct applications to cryptography and proof complexity via connections by Bauer, Farshim, and Mazaheri (CRYPTO 2018) and Itsykson and Riazanov (CCC 2021). Our proof technique could be of independent interest as it is an extension of simulation methods to non-lifted functions. Previously, simulations have been widely applied to lifted functions (a.k.a composed functions), which leads to beautiful query-to- communication lifting theorems. However, many important communication problems are not lifted functions. We believe our methods could give more applications. In particular, it may have applications to communication complexity of search problems with many solutions. Note that many existing methods do not apply to this setting.

Details

EAAI Journal 2024 Journal Article

Cross-domain self-supervised few-shot learning via multiple crops with teacher-student network

Guangpeng Wang
Yongxiong Wang
Jiapeng Zhang
Xiaoming Wang
Zhiqun Pan

Most few-shot learning(FSL) methods rely on a pre-trained network on a large annotated base dataset with a feature distribution similar to that of the target domain. Conventional transfer learning and traditional few-shot learning methods are ineffective when there is a large gap between the source and target domain. We propose a simple teacher-student network solution to facilitate unlabeled images from the target domain to alleviate domain gap. We impose a self-supervised loss by calculating predictions from large crops of the unannotated samples of target domain using a teacher network and matching them with small crops of the same images from a student network. Furthermore, we design a novel contrastive loss for large crops to sufficiently utilize the self-supervised information of unlabeled images on target domain for the model training. The feature representation can be easily generalized to the target domain without the pretraining phase on target-specific classes. The accuracies of our model are 23. 61 ± 0. 42, 33. 87 ± 0. 59, 63. 21 ± 0. 88, 74. 36 ± 0. 88 on ChestX, ISIC, EuroSAT, and CropDisease datasets for the 1-shot scenario respectively. Extensive experiments show that the proposed method achieves competitive performance on the challenging cross-domain FSL image classification.

Details DOI

SODA Conference 2024 Conference Paper

Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms

Chandra Sekhar Mukherjee
Jiapeng Zhang

Community detection in the stochastic block model is one of the central problems of graph clustering. Since its introduction by Holland, Laskey, and Leinhardt (Social Networks, 1983), many subsequent papers have made great strides in solving and understanding this model. However, despite the long history of study, there are still unsolved challenges. In this direction, two primary open problems are: how to recover large clusters in the presence of small clusters (we call it small cluster barrier), and how to analyze simple and practical spectral algorithms (we call them vanilla spectral algorithms), especially when the number of communities is large. In this paper, we use a power iteration approach to make progress in both these directions. To this end, we design the first parameter-free community recovery algorithm that recovers large clusters in the presence of small clusters. Our algorithm only compares the rows of the powered adjacency matrix and has a recovery guarantee poly-logarithmically close to that of the state-of-the-art algorithms in this problem that require knowledge of model parameters. Then based on a connection between the powered adjacency matrix and eigenvectors, we provide a “vanilla” spectral algorithm in the balanced case when the number of communities is large. This answers an open question by Van Vu (Combinatorics Probability and Computing, 2018) in the balanced case. Our methods also partially solve technical barriers discussed by Abbe, Fan, Wang, and Zhong (Annals of Statistics, 2020). On the technical side, we introduce a random partition method to analyze each entry of a powered random matrix. This method can be viewed as an eigenvector version of Wigner's trace method. Recall that Wigner's trace method links the trace of the powered matrix to the matrix's eigenvalues. Our method links the whole powered matrix to the span of eigenvectors. We expect our method to have more applications in random matrix theory.

Details

NeurIPS Conference 2023 Conference Paper

On the Power of SVD in the Stochastic Block Model

Xinyu Mao
Jiapeng Zhang

A popular heuristic method for improving clustering results is to apply dimensionality reduction before running clustering algorithms. It has been observed that spectral-based dimensionality reduction tools, such as PCA or SVD, improve the performance of clustering algorithms in many applications. This phenomenon indicates that spectral method not only serves as a dimensionality reduction tool, but also contributes to the clustering procedure in some sense. It is an interesting question to understand the behavior of spectral steps in clustering problems. As an initial step in this direction, this paper studies the power of vanilla-SVD algorithm in the stochastic block model (SBM). We show that, in the symmetric setting, vanilla-SVD algorithm recovers all clusters correctly. This result answers an open question posed by Van Vu (Combinatorics Probability and Computing, 2018) in the symmetric setting.

PDF Details

NeurIPS Conference 2023 Conference Paper

Recovering Unbalanced Communities in the Stochastic Block Model with Application to Clustering with a Faulty Oracle

Chandra Sekhar Mukherjee
Pan Peng
Jiapeng Zhang

The stochastic block model (SBM) is a fundamental model for studying graph clustering or community detection in networks. It has received great attention in the last decade and the balanced case, i. e. , assuming all clusters have large size, has been well studied. However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still limited. In this paper, we provide a simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes. We improve upon a result of Ailon, Chen and Xu [ICML 2013; JMLR 2015] by removing the assumption that there is a large interval such that the sizes of clusters do not fall in, and also remove the dependency of the size of the recoverable clusters on the number of underlying clusters. We further complement our theoretical improvements with experimental comparisons. Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to poly-logarithmic factors) when the probability parameters are constant. As a byproduct, we obtain an efficient clustering algorithm with sublinear query complexity in a faulty oracle model, which is capable of detecting all clusters larger than $\tilde{\Omega}({\sqrt{n}})$, even in the presence of $\Omega(n)$ small clusters in the graph. In contrast, previous efficient algorithms that use a sublinear number of queries are incapable of recovering any large clusters if there are more than $\tilde{\Omega}(n^{2/5})$ small clusters.

PDF Details

FOCS Conference 2023 Conference Paper

Streaming Lower Bounds and Asymmetric Set-Disjointness

Shachar Lovett
Jiapeng Zhang

Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in the case where the data stream is given in a random order, or is stochastic, only weaker lower bounds exist. In this work we close this gap, up to logarithmic factors. In order to do so we consider the needle problem, which is a natural hard problem for frequency estimation studied in (Andoni et al. 2008, Crouch et al. 2016). Here, the goal is to distinguish between two distributions over data streams with t samples. The first is uniform over a large enough domain. The second is a planted model; a secret “needle“ is uniformly chosen, and then each element in the stream equals the needle with probability p, and otherwise is uniformly chosen from the domain. It is simple to design streaming algorithms that distinguish the distributions using space $s \approx 1 /\left(p^{2} t\right)$. It was unclear if this is tight, as the existing lower bounds are weaker. We close this gap and show that the trade-off is near optimal, up to a logarithmic factor. Our proof builds and extends classical connections between streaming algorithms and communication complexity, concretely multi-party unique set-disjointness. We introduce two new ingredients that allow us to prove sharp bounds. The first is a lower bound for an asymmetric version of multi-party unique set-disjointness, where players receive input sets of different sizes, and where the communication of each player is normalized relative to their input length. The second is a combinatorial technique that allows to sample needles in the planted model by first sampling intervals, and then sampling a uniform needle in each interval.

Details

TMLR Journal 2023 Journal Article

The (Un)Scalability of Informed Heuristic Function Estimation in NP-Hard Search Problems

Sumedh Pendurkar
Taoan Huang
Brendan Juba
Jiapeng Zhang
Sven Koenig
Guni Sharon

The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with a completely informed heuristic function, A* can solve such problems in time complexity that is polynomial in the solution cost and branching factor. In light of this fact, we examine a line of recent publications that propose fitting deep neural networks to the completely informed heuristic function. We assert that these works suffer from inherent scalability limitations since --- under the assumption of NP $\not \subseteq$ P/poly --- such approaches result in either (a) network sizes that scale super-polynomially in the instance sizes or (b) the accuracy of the fitted deep neural networks scales inversely with the instance sizes. Complementing our theoretical claims, we provide experimental results for three representative NP-hard search problems. The results suggest that fitting deep neural networks to informed heuristic functions requires network sizes that grow quickly with the problem instance size. We conclude by suggesting that the research community should focus on scalable methods for integrating heuristic search with machine learning, as opposed to methods relying on informed heuristic estimation.

PDF Details

STOC Conference 2020 Conference Paper

Decision list compression by mild random restrictions

Shachar Lovett
Kewen Wu 0001
Jiapeng Zhang

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whose term is satisfied by the input. Decision lists generalize both CNFs and DNFs, and have been studied both in complexity theory and in learning theory.

Details

STOC Conference 2020 Conference Paper

Improved bounds for the sunflower lemma

Ryan Alweiss
Shachar Lovett
Kewen Wu 0001
Jiapeng Zhang

A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all. Erdős and Rado proved the sunflower lemma: for any fixed r , any family of sets of size w , with at least about w w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c w for some constant c . In this paper, we improve the bound to about (log w ) w . In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is tight up to lower order terms.

Details

STOC Conference 2019 Conference Paper

DNF sparsification beyond sunflowers

Shachar Lovett
Jiapeng Zhang

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in the size). The other direction is much less clear.

Details

STOC Conference 2019 Conference Paper

Quantum Lovász local lemma: Shearer's bound is tight

Kun He 0011
Qian Li 0012
Xiaoming Sun 0001
Jiapeng Zhang

Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all “bad” events under some “weakly dependent” condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science. A tight criterion under which the abstract version LLL (ALLL) holds was given by Shearer. It turns out that Shearer’s bound is generally not tight for variable version LLL (VLLL). Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem. In this paper, we prove that Shearer’s bound is tight for QLLL, i.e., the relative dimension of the smallest satisfying subspace is completely characterized by the independent set polynomial, affirming a conjecture proposed by Sattath et al. Our result also shows the tightness of Gilyén and Sattath’s algorithm, and implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits. Commuting LLL (CLLL), LLL for commuting local Hamiltonians which are widely studied in the literature, is also investigated here. We prove that the tight regions of CLLL and QLLL are different in general. This result might imply that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer’s bound. In applications of LLLs, the symmetric cases are most common, i.e., the events are with the same probability and the Hamiltonians are with the same relative dimension. We give the first lower bound on the gap between the symmetric VLLL and Shearer’s bound. Our result can be viewed as a quantitative study on the separation between quantum and classical constraint satisfaction problems. Additionally, we obtain similar results for the symmetric CLLL. As an application, we give lower bounds on the critical thresholds of VLLL and CLLL for several of the most common lattices.

Details

SODA Conference 2018 Conference Paper

The Robust Sensitivity of Boolean Functions

Shachar Lovett
Avishay Tal
Jiapeng Zhang

The sensitivity conjecture is one of the central open problems in Boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a Boolean function to moments of its sensitivity. We prove the robust sensitivity conjecture in this work with near optimal parameters.

Details

FOCS Conference 2017 Conference Paper

Active Classification with Comparison Queries

Daniel M. Kane
Shachar Lovett
Shay Moran
Jiapeng Zhang

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a specific restaurant (a label query); or which one of two restaurants did she like more (a comparison query). We focus on the class of half spaces, and show that under natural assumptions, such as large margin or bounded bit-description of the input examples, it is possible to reveal all the labels of a sample of size n using approximately O(log n) queries. This implies an exponential improvement over classical active learning, where only label queries are allowed. We complement these results by showing that if any of these assumptions is removed then, in the worst case, Ω(n) queries are required. Our results follow from a new general framework of active learning with additional queries. We identify a combinatorial dimension, called the inference dimension, that captures the query complexity when each additional query is determined by O(1) examples (such as comparison queries, each of which is determined by the two compared examples). Our results for half spaces follow by bounding the inference dimension in the cases discussed above.

Details

STOC Conference 2015 Conference Paper

Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions

Shachar Lovett
Jiapeng Zhang

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in {0,1} n with support of size k, and given access only to noisy samples from it, where each bit is flipped independently with probability (1-μ)/2, estimate the original probability up to an additive error of ε. We give an algorithm which solves this problem in time polynomial in (k log log k , n, 1/ε). This improves on the previous algorithm of Wigderson and Yehudayoff [FOCS 2012] which solves the problem in time polynomial in (k log k , n, 1/ε). Our main technical contribution, which facilitates the algorithm, is a new reverse Bonami-Beckner inequality for the L 1 norm of sparse functions.

Details