Pan Peng

Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

Pan Peng, Hangyu Xu

We study the problem of releasing a differentially private (DP) synthetic graph $G^{'}$ that well approximates the triangle-motif sizes of all cuts of any given graph $G$ , where a mot…

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT

Yinhao Dong, Pan Peng, Ali Vakilian

We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a $1/2$ -approximation for estimating the va…

cs.DS2022

Sublinear-Time Algorithms for Max Cut, Max E2Lin $(q)$ , and Unique Label Cover on Expanders

Pan Peng, Yuichi Yoshida

We show sublinear-time algorithms for Max Cut and Max E2Lin $(q)$ on expanders in the adjacency list model that distinguishes instances with the optimal value more than $1-\varepsil…

An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs

Pan Peng, Yuyang Wang

We revisit the relation between two fundamental property testing models for bounded-degree directed graphs: the bidirectional model in which the algorithms are allowed to query bot…

cs.DS2019

Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs

Pan Peng

Due to the massive size of modern network data, local algorithms that run in sublinear time for analyzing the cluster structure of the graph are receiving growing interest. Two typ…

cs.LO2023

On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing

Isolde Adler, Noleen KÃ¶hler, Pan Peng

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…

An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs

Pan Peng, Yuyang Wang, Joy Qiping Yang +1

We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\var…

cs.DS2018

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs

Gramoz Goranci, Monika Henzinger, Pan Peng

We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an $n^{c}$ -separator theorem for so…

math.AG2004

A simple proof of Gopakumar-Vafa conjecture for local toric Calabi-Yau manifolds

Pan Peng

We prove Gopakumar-Vafa conjecture for local toric Calabi-Yau manifolds. It's also proved that the local Gopakumar-Vafa invariants of a given class at large genus vanish.

cs.CC2021

GSF-locality is not sufficient for proximity-oblivious testing

Isolde Adler, Noleen KÃ¶hler, Pan Peng

In Property Testing, proximity-oblivious testers (POTs) form a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on…

cs.DS2020

Average Sensitivity of Spectral Clustering

Pan Peng, Yuichi Yoshida

Spectral clustering is one of the most popular clustering methods for finding clusters in a graph, which has found many applications in data mining. However, the input graph in tho…

math.GT2015

Congruent skein relations for colored HOMFLY-PT invariants and colored Jones polynomials

Qingtao Chen, Kefeng Liu, Pan Peng +1

Colored HOMFLY-PT invariant, the generalization of the colored Jones polynomial, is one of the most important quantum invariants of links. This paper is devoted to investigating th…

cs.DS2018

Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty

Hendrik Fichtenberger, Pan Peng, Christian Sohler

One of the most fundamental questions in graph property testing is to characterize the combinatorial structure of properties that are testable with a constant number of queries. We…

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…

cs.DS2022

Approximately Counting Subgraphs in Data Streams

Hendrik Fichtenberger, Pan Peng

Estimating the number of subgraphs in data streams is a fundamental problem that has received great attention in the past decade. In this paper, we give improved streaming algorith…

math.PR2011

The Small-Community Phenomenon in Networks

Angsheng Li, Pan Peng

We investigate several geometric models of network which simultaneously have some nice global properties, that the small diameter property, the small-community phenomenon, which is…

math.GT2010

New Structure of Knot Invariants

Kefeng Liu, Pan Peng

Based on the proof of Labastida-Mari{Ã±}o-Ooguri-Vafa conjecture \cite{lmov}, we derive an infinite product formula for Chern-Simons partition functions, the generating function of…

cs.DS2013

Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure

Angsheng Li, Pan Peng

We study the problem of finding and characterizing subgraphs with small \textit{bipartiteness ratio}. We give a bicriteria approximation algorithm \verb|SwpDB| such that if there e…

cs.LG2018

Mixed-Order Spectral Clustering for Networks

Yan Ge, Haiping Lu, Pan Peng

Clustering is fundamental for gaining insights from complex networks, and spectral clustering (SC) is a popular approach. Conventional SC focuses on second-order structures (e.g.,…

cs.LG2023

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…

math.QA2009

Proof of the Labastida-Marino-Ooguri-Vafa Conjecture

Kefeng Liu, Pan Peng

Based on large N Chern-Simons/topological string duality, in a series of papers, J.M.F. Labastida, M. Marino, H. Ooguri and C. Vafa conjectured certain remarkable new algebraic str…

cs.LG2025

Average Sensitivity of Hierarchical $k$ -Median Clustering

Shijie Li, Weiqiang He, Ruobing Bai +1

Hierarchical clustering is a widely used method for unsupervised learning with numerous applications. However, in the application of modern algorithms, the datasets studied are usu…

cs.DS2016

Dynamic Graph Stream Algorithms in $o (n)$ Space

Zengfeng Huang, Pan Peng

In this paper we study graph problems in dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require $Î©(n)…

quant-ph2026

Quantum Property Testing for Bounded-Degree Directed Graphs

Pan Peng, Jingyu Wu

We study quantum property testing for directed graphs with maximum in-degree and out-degree bounded by some universal constant $d$ . For a proximity parameter $ε$ , we show…

cs.DS2019

Constant-Time Dynamic $(I^ + 1)$ -Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing

Monika Henzinger, Pan Peng

With few exceptions (namely, algorithms for maximal matching, $2$ -approximate vertex cover, and certain constant-stretch spanners), all known fully dynamic algorithms in general gr…

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs

Pan Peng, Christian Sohler, Yi Xu

Single-linkage clustering is a fundamental method for data analysis. Algorithmically, one can compute a single-linkage $k$ -clustering (a partition into $k$ clusters) by computing a…

cs.SI2024

Sublinear-Time Opinion Estimation in the Friedkin--Johnsen Model

Stefan Neumann, Yinhao Dong, Pan Peng

Online social networks are ubiquitous parts of modern societies and the discussions that take place in these networks impact people's opinions on diverse topics, such as politics o…

Four-Cycle Counting in Low-Degeneracy Graph Streams

Sebastian LÃ¼derssen, Stefan Neumann, Pan Peng

We study the problem of $(1 + ε)$ -approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling i…

physics.atom-ph2025

Diffraction of fast heavy noble gas atoms, Ar, Kr and Xe on a LiF(001) surface Changing the tip of a 'perfect' AFM

Debiossac Maxime, Pan Peng, Kanitz Carina +1

We investigate experimentally the diffraction of fast atoms of noble gas on a LiF(100) crystal oriented along the [100] and [110] directions. The wavelengths are so short that the…

Testable Bounded Degree Graph Properties Are Random Order Streamable

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng +1

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degre…

Near-Optimal Four-Cycle Counting in Graph Streams

Sebastian LÃ¼derssen, Stefan Neumann, Pan Peng

We study four-cycle counting in arbitrary order graph streams. We present a 3-pass algorithm for $(1 + ε)$ -approximating the number of four-cycles using $\widetilde{O}(m/\s…

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs

Pan Peng, Yuyang Wang

We study \emph{local computation algorithms (LCAs)} for constructing spanning trees. In this setting, the goal is to locally determine, for each edge $e \in E$ , whether it belong…

math.GT2010

On a proof of the Labastida-Marino-Ooguri-Vafa conjecture

Kefeng Liu, Pan Peng

We outline a proof of a remarkable conjecture of Labastida-Mari{Ã±}o-Ooguri-Vafa about certain new algebraic structures of quantum link invariants and the integrality of infinite f…

cs.DS2015

Testing Cluster Structure of Graphs

Artur Czumaj, Pan Peng, Christian Sohler

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter $ε$ , a $d$ -bounde…

cs.DS2022

Sublinear-Time Clustering Oracle for Signed Graphs

Stefan Neumann, Pan Peng

Social networks are often modeled using signed graphs, where vertices correspond to users and edges have a sign that indicates whether an interaction between users was positive or…

cs.DS2021

Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time

Hendrik Fichtenberger, Mingze Gao, Pan Peng

We present a simple sublinear-time algorithm for sampling an arbitrary subgraph $H$ \emph{exactly uniformly} from a graph $G$ with $m$ edges, to which the algorithm has access by p…

cs.DS2024

A Differentially Private Clustering Algorithm for Well-Clustered Graphs

Weiqiang He, Hendrik Fichtenberger, Pan Peng

We study differentially private (DP) algorithms for recovering clusters in well-clustered graphs, which are graphs whose vertex set can be partitioned into a small number of sets,…

cs.NE2021

Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem

Jakob Bossek, Frank Neumann, Pan Peng +1

We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the…

Improved Guarantees for Vertex Sparsification in Planar Graphs

Gramoz Goranci, Monika Henzinger, Pan Peng

Graph Sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e…

cs.DS2020

Augmenting the Algebraic Connectivity of Graphs

Bogdan-Adrian Manghiuc, Pan Peng, He Sun

For any undirected graph $G = (V, E)$ and a set $E_{W}$ of candidate edges with $E \cap E_{W} = \emptyset$ , the $(k, I^^{3})$ -spectral augmentability problem is to find a set $F$ of $k$ edges fro…

Massively Parallel Algorithms for the Stochastic Block Model

Zelin Li, Pan Peng, Xianbin Zhu

Learning the community structure of a large-scale graph is a fundamental problem in machine learning, computer science and statistics. We study the problem of exactly recovering th…

quant-ph2026

Quantum Algorithms for Triangle Cut Sparsification

Shan Jiang, Pan Peng

Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale…

Sublinear Spectral Clustering Oracle with Little Memory

Ranran Shen, Xiaoyi Zhu, Pan Peng +1

We study the problem of designing \emph{sublinear spectral clustering oracles} for well-clusterable graphs. Such an oracle is an algorithm that, given query access to the adjacency…

Streaming Max-Cut in General Metrics

Shaofeng H. -C. Jiang, Pan Peng, Haoze Wang

Max-Cut is a fundamental combinatorial optimization problem that has been studied in various computational settings. We initiate the study of its streaming complexity in \emph{gene…

cs.DS2015

Testing Small Set Expansion in General Graphs

Angsheng Li, Pan Peng

We consider the problem of testing small set expansion for general graphs. A graph $G$ is a $(k, I ¨ )$ -expander if every subset of volume at most $k$ has conductance at least $I ¨ $ . S…

A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time

Ranran Shen, Pan Peng

We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain $k$ latent clusters, each charact…

Effective Resistances in Non-Expander Graphs

Dongrun Cai, Xue Chen, Pan Peng

Effective resistances are ubiquitous in graph algorithms and network analysis. In this work, we study sublinear time algorithms to approximate the effective resistance of an adjace…

cs.DS2021

Local Algorithms for Estimating Effective Resistance

Pan Peng, Daniel Lopatta, Yuichi Yoshida +1

Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and netwo…

cs.DS2018

Spectral concentration and greedy k-clustering

Tamal K. Dey, Pan Peng, Alfred Rossi +1

A popular graph clustering method is to consider the embedding of an input graph into R^k induced by the first k eigenvectors of its Laplacian, and to partition the graph via geome…

Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model

Weiming Feng, Zelin Li, Pan Peng

We study sublinear-time algorithms for solving linear systems $S z = b$ , where $S$ is a diagonally dominant matrix, i.e., $∣ S_{ii} ∣ \geq I^´ + \sum_{j \neq = i} ∣ S_{ij} ∣$ for all $i \in…

cs.LO2021

On Testability of First-Order Properties in Bounded-Degree Graphs

Isolde Adler, Noleen KÃ¶hler, Pan Peng

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…

Learning-Augmented Streaming Algorithms for Correlation Clustering

Yinhao Dong, Shan Jiang, Shi Li +1

We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partit…

cs.DS2021

Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest

Monika Henzinger, Pan Peng

We give two fully dynamic algorithms that maintain a $(1 + ε)$ -approximation of the weight $M$ of a minimum spanning forest (MSF) of an $n$ -node graph $G$ with edges weight…

cs.LG2021

Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle

Pan Peng, Jiapeng Zhang

Motivated by applications in crowdsourced entity resolution in database, signed edge prediction in social networks and correlation clustering, Mazumdar and Saha [NIPS 2017] propose…

Estimating Graph Parameters from Random Order Streams

Pan Peng, Christian Sohler

We develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming algorithms. We illustrate…

The Power of Vertex Sparsifiers in Dynamic Graph Algorithms

Gramoz Goranci, Monika Henzinger, Pan Peng

We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsifica…