Pan Peng (彭攀)
I am a faculty member (特任教授) in the School of Computer Science and Technology of University of Science and Technology of China (USTC).
I was a long-term participant at UC Berkeley's Simons Institute program in Sublinear Algorithms. I was a lecturer (assistant professor) in the Department of Computer Science at University of Sheffield, UK. Before that, I held postdoc positions of TU Dortmund, Germany at the research group of Prof. Christian Sohler and University of Vienna, Austria at the research group of Prof. Monika Henzinger. I got my Ph.D under supervision of Prof. Angsheng Li, in the Institute of Software, Chinese Academy of Sciences in 2013. I received my bachelor degree in Mathematics from Beijing Normal University in 2007.
|
|
My research interests lie at the intersection of theoretical computer science, network science, and data science. Currently, I am focused on sublinear algorithms, graph algorithms, and the privacy and robustness of algorithms.
Program Committees:
WALCOM 2025, RANDOM 2024, IJTCS-FAW 2024, STACS 2024, WAW 2024, WAW 2023, SWAT 2022, LATIN 2020, IJCAI 2019, AAAI 2019, TAMC 2019,
FAW 2019, WAW 2019,
FAW 2018, WAW 2018, WAW 2017, WAW 2016, TAMC 2016, WAW 2015, TAMC 2015, WAW 2014, TAMC 2014
Publications:
A Differentially Private Clustering Algorithm for Well-Clustered Graphs.
Weiqiang He, Hendrik Fichtenberger, Pan Peng.
In the eleventh International Conference on Learning Representations (ICLR 2024). Arxiv Version.
Sublinear-Time Opinion Estimation in the Friedkin–Johnsen Model.
Stefan Neumann, Yinhao Dong, and Pan Peng.
In the 2024 ACM Web Conference (WebConf, formerly WWW 2024). Arxiv Version.
A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time.
Ranran Shen, Pan Peng.
In the thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023). Arxiv Version.
Recovering Unbalanced Communities in the Stochastic Block Model with Application to Clustering with a Faulty Oracle.
Chandra Sekhar Mukherjee, Pan Peng, Jiapeng Zhang.
In the thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023). Arxiv Version.
Sublinear-Time Algorithms for Max Cut, Max E2Lin$(q)$, and Unique Label Cover on Expanders.
Pan Peng, Yuichi Yoshida.
In the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Arxiv Version.
An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs.
Pan Peng, Yuyang Wang.
In the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Arxiv Version.
Massively Parallel Algorithms for the Stochastic Block Model.
Zelin Li, Pan Peng, Xianbin Zhu.
In the 31st Annual European Symposium on Algorithms (ESA 2023). Arxiv Version.
Effective Resistances in Non-Expander Graphs.
Dongrun Cai, Xue Chen, Pan Peng.
In the 31st Annual European Symposium on Algorithms (ESA 2023). Arxiv Version.
Sublinear-Time Clustering Oracle for Signed Graphs.
Stefan Neumann, Pan Peng.
In the 39th International Conference on Machine Learning (ICML 2022). Arxiv Version.
(Accepted for long presentation.)
Approximately Counting Subgraphs in Data Streams.
Hendrik Fichtenberger, Pan Peng.
In the 41st ACM Symposium on Principles of Database Systems (PODS 2022). Arxiv Version.
Local Algorithms for Estimating Effective Resistance.
Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci.
In the 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2021). Arxiv Version.
Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle.
Pan Peng, Jiapeng Zhang.
In the 34th Annual Conference on Learning Theory (COLT 2021). Arxiv Version.
GSF-Locality Is Not Sufficient for Proximity-Oblivious Testing.
Isolde Adler, Noleen Köhler, Pan Peng.
In the Computational Complexity Conference (CCC 2021). Arxiv Version.
See the comments in Oded Goldreich's Choices #304.
On Testability of First-Order Properties in Bounded-Degree Graphs.
Isolde Adler, Noleen Köhler, Pan Peng.
In the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021). Arxiv Version.
Mixed-Order Spectral Clustering for Complex Networks.
Yan Ge, Pan Peng, Haiping Lu.
In Pattern Recognition 2021. DOI.
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.
Monika Henzinger, Pan Peng.
In Inf. Comput. 2021. DOI. Arxiv Version.
Augmenting the Algebraic Connectivity of Graphs.
Bogdan Manghiuc, Pan Peng, He Sun.
In Proceedings of the 28th European Symposium on Algorithms (ESA 2020). Arxiv Version.
Testable Properties in General Graphs and Random Order Streaming.
Artur Czumaj, Hendrik Fichtenberger, Pan Peng, Christian Sohler.
In the 24th International Conference on Randomization and Computation (RANDOM 2020). Arxiv Version.
Average Sensitivity of Spectral Clustering.
Pan Peng and Yuichi Yoshida.
In the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2020). Arxiv Version.
Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time.
Hendrik Fichtenberger, Mingze Gao and Pan Peng.
In the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020). Arxiv Version.
More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization.
Jakob Bossek, Frank Neumann, Pan Peng and Dirk Sudholt.
In the Genetic and Evolutionary Computation Conference (GECCO 2020). Arxiv Version.
Constant-Time Dynamic $(\Delta+1)$-Coloring.
Monika Henzinger, Pan Peng.
In the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Part I of Arxiv Version.
In ACM Trans. Algorithms 2022.
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs.
Pan Peng.
In the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). Arxiv Version.
Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring.
Jakob Bossek, Frank Neumann, Pan Peng and Dirk Sudholt.
In Algorithmica 2021 (version titled "Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem").
In the Genetic and Evolutionary Computation Conference (GECCO 2019). DOI.
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty.
Hendrik Fichtenberger, Pan Peng and Christian Sohler.
In the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). Arxiv Version.
Spectral Concentration and Greedy k-Clustering.
Tamal K. Dey, Pan Peng, Alfred Rossi, Anastasios Sidiropoulos.
Computational Geometry: Theory and Applications (Comput. Geom. 2019). Arxiv Version.
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.
Gramoz Goranci, Monika Henzinger, Pan Peng.
In Proceedings of the 26th European Symposium on Algorithms (ESA 2018). Arxiv version.
Estimating Graph Parameters from Random Order Streams.
Pan Peng, Christian Sohler.
In the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). Arxiv version.
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.
Gramoz Goranci, Monika Henzinger, Pan Peng.
In the 25th Annual European Symposium on Algorithms (ESA 2017). Arxiv version.
Improved Guarantees for Vertex Sparsification in Planar Graphs.
Gramoz Goranci, Monika Henzinger, Pan Peng.
In SIAM Journal on Discrete Mathematics (SIDMA) 2020.
In the 25th Annual European Symposium on Algorithms (ESA 2017). Arxiv version.
Testable Bounded Degree Graph Properties Are Random Order Streamable.
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng and Christian Sohler.
In the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Arxiv version.
Dynamic Graph Stream Algorithms in o(n) Space.
Zengfeng Huang, Pan Peng.
In Algorithmica 2019.
In the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Arxiv version.
Relating Two Property Testing Models for Bounded Degree Directed Graphs.
Artur Czumaj, Pan Peng, Christian Sohler.
In 48th ACM Symposium on Theory of Computing (STOC 2016). DOI.
On Constant Size Graphs That Preserve the Local Structure of High Girth Graphs.
Hendrik Fichtenberger, Pan Peng and Christian Sohler.
In the 19th International Workshop on Randomization and Computation (RANDOM'2015). DOI.
Testing Cluster Structure of Graphs.
Artur Czumaj, Pan Peng, Christian Sohler.
In 47th ACM Symposium on Theory of Computing (STOC 2015). Arxiv version.
Testing Small Set Expansion in General Graphs.
Angsheng Li, Pan Peng.
In 32nd Symposium on Theoretical Aspects of Computer Science (STACS 2015). Arxiv version.
Equilibrium Games in Networks.
Angsheng Li, Xiaohui Zhang, Yicheng Pan, Pan Peng.
Physica A: Statistical Mechanics and its Applications, Volume 416, Pages 49-60, 2014. DOI.
Global Core, and Galaxy Structure of Networks.
Wei Zhang, Yicheng Pan, Pan Peng, Jiankou Li, Xuechen Li, Angsheng Li.
SCIENCE CHINA Information Sciences 57(7): 1-20 (2014). DOI.
Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure.
Angsheng Li, Pan Peng.
In 24th International Symposium on Algorithms and Computation (ISAAC 2013). Arxiv version.
A Local Algorithm for Finding Dense Bipartite-Like Subgraphs.
Pan Peng.
In 18th Annual International Computing and Combinatorics Conference (COCOON 2012). DOI.
The Small Community Phenomenon in Networks: Models, Algorithms and Applications.
Pan Peng.
In 9th Annual Conference on Theory and Applications of Models of Computation (TAMC 2012). DOI.
The Small-Community Phenomenon in Networks.
Angsheng Li, Pan Peng.
Mathematical Structures in Computer Sciences 22, pp 373-407, 2012. Arxiv version.
Community Structures in Classical Network Models.
Angsheng Li, Pan Peng.
Internet Mathematics 7(2), 2011. DOI
Weiqiang He, Hendrik Fichtenberger, Pan Peng.
In the eleventh International Conference on Learning Representations (ICLR 2024). Arxiv Version.
Sublinear-Time Opinion Estimation in the Friedkin–Johnsen Model.
Stefan Neumann, Yinhao Dong, and Pan Peng.
In the 2024 ACM Web Conference (WebConf, formerly WWW 2024). Arxiv Version.
A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time.
Ranran Shen, Pan Peng.
In the thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023). Arxiv Version.
Recovering Unbalanced Communities in the Stochastic Block Model with Application to Clustering with a Faulty Oracle.
Chandra Sekhar Mukherjee, Pan Peng, Jiapeng Zhang.
In the thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023). Arxiv Version.
Sublinear-Time Algorithms for Max Cut, Max E2Lin$(q)$, and Unique Label Cover on Expanders.
Pan Peng, Yuichi Yoshida.
In the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Arxiv Version.
An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs.
Pan Peng, Yuyang Wang.
In the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Arxiv Version.
Massively Parallel Algorithms for the Stochastic Block Model.
Zelin Li, Pan Peng, Xianbin Zhu.
In the 31st Annual European Symposium on Algorithms (ESA 2023). Arxiv Version.
Effective Resistances in Non-Expander Graphs.
Dongrun Cai, Xue Chen, Pan Peng.
In the 31st Annual European Symposium on Algorithms (ESA 2023). Arxiv Version.
Sublinear-Time Clustering Oracle for Signed Graphs.
Stefan Neumann, Pan Peng.
In the 39th International Conference on Machine Learning (ICML 2022). Arxiv Version.
(Accepted for long presentation.)
Approximately Counting Subgraphs in Data Streams.
Hendrik Fichtenberger, Pan Peng.
In the 41st ACM Symposium on Principles of Database Systems (PODS 2022). Arxiv Version.
Local Algorithms for Estimating Effective Resistance.
Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci.
In the 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2021). Arxiv Version.
Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle.
Pan Peng, Jiapeng Zhang.
In the 34th Annual Conference on Learning Theory (COLT 2021). Arxiv Version.
GSF-Locality Is Not Sufficient for Proximity-Oblivious Testing.
Isolde Adler, Noleen Köhler, Pan Peng.
In the Computational Complexity Conference (CCC 2021). Arxiv Version.
See the comments in Oded Goldreich's Choices #304.
On Testability of First-Order Properties in Bounded-Degree Graphs.
Isolde Adler, Noleen Köhler, Pan Peng.
In the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021). Arxiv Version.
Mixed-Order Spectral Clustering for Complex Networks.
Yan Ge, Pan Peng, Haiping Lu.
In Pattern Recognition 2021. DOI.
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.
Monika Henzinger, Pan Peng.
In Inf. Comput. 2021. DOI. Arxiv Version.
Augmenting the Algebraic Connectivity of Graphs.
Bogdan Manghiuc, Pan Peng, He Sun.
In Proceedings of the 28th European Symposium on Algorithms (ESA 2020). Arxiv Version.
Testable Properties in General Graphs and Random Order Streaming.
Artur Czumaj, Hendrik Fichtenberger, Pan Peng, Christian Sohler.
In the 24th International Conference on Randomization and Computation (RANDOM 2020). Arxiv Version.
Average Sensitivity of Spectral Clustering.
Pan Peng and Yuichi Yoshida.
In the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2020). Arxiv Version.
Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time.
Hendrik Fichtenberger, Mingze Gao and Pan Peng.
In the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020). Arxiv Version.
More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization.
Jakob Bossek, Frank Neumann, Pan Peng and Dirk Sudholt.
In the Genetic and Evolutionary Computation Conference (GECCO 2020). Arxiv Version.
Constant-Time Dynamic $(\Delta+1)$-Coloring.
Monika Henzinger, Pan Peng.
In the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Part I of Arxiv Version.
In ACM Trans. Algorithms 2022.
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs.
Pan Peng.
In the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). Arxiv Version.
Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring.
Jakob Bossek, Frank Neumann, Pan Peng and Dirk Sudholt.
In Algorithmica 2021 (version titled "Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem").
In the Genetic and Evolutionary Computation Conference (GECCO 2019). DOI.
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty.
Hendrik Fichtenberger, Pan Peng and Christian Sohler.
In the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019). Arxiv Version.
Spectral Concentration and Greedy k-Clustering.
Tamal K. Dey, Pan Peng, Alfred Rossi, Anastasios Sidiropoulos.
Computational Geometry: Theory and Applications (Comput. Geom. 2019). Arxiv Version.
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.
Gramoz Goranci, Monika Henzinger, Pan Peng.
In Proceedings of the 26th European Symposium on Algorithms (ESA 2018). Arxiv version.
Estimating Graph Parameters from Random Order Streams.
Pan Peng, Christian Sohler.
In the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). Arxiv version.
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.
Gramoz Goranci, Monika Henzinger, Pan Peng.
In the 25th Annual European Symposium on Algorithms (ESA 2017). Arxiv version.
Improved Guarantees for Vertex Sparsification in Planar Graphs.
Gramoz Goranci, Monika Henzinger, Pan Peng.
In SIAM Journal on Discrete Mathematics (SIDMA) 2020.
In the 25th Annual European Symposium on Algorithms (ESA 2017). Arxiv version.
Testable Bounded Degree Graph Properties Are Random Order Streamable.
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng and Christian Sohler.
In the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Arxiv version.
Dynamic Graph Stream Algorithms in o(n) Space.
Zengfeng Huang, Pan Peng.
In Algorithmica 2019.
In the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Arxiv version.
Relating Two Property Testing Models for Bounded Degree Directed Graphs.
Artur Czumaj, Pan Peng, Christian Sohler.
In 48th ACM Symposium on Theory of Computing (STOC 2016). DOI.
On Constant Size Graphs That Preserve the Local Structure of High Girth Graphs.
Hendrik Fichtenberger, Pan Peng and Christian Sohler.
In the 19th International Workshop on Randomization and Computation (RANDOM'2015). DOI.
Testing Cluster Structure of Graphs.
Artur Czumaj, Pan Peng, Christian Sohler.
In 47th ACM Symposium on Theory of Computing (STOC 2015). Arxiv version.
Testing Small Set Expansion in General Graphs.
Angsheng Li, Pan Peng.
In 32nd Symposium on Theoretical Aspects of Computer Science (STACS 2015). Arxiv version.
Equilibrium Games in Networks.
Angsheng Li, Xiaohui Zhang, Yicheng Pan, Pan Peng.
Physica A: Statistical Mechanics and its Applications, Volume 416, Pages 49-60, 2014. DOI.
Global Core, and Galaxy Structure of Networks.
Wei Zhang, Yicheng Pan, Pan Peng, Jiankou Li, Xuechen Li, Angsheng Li.
SCIENCE CHINA Information Sciences 57(7): 1-20 (2014). DOI.
Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure.
Angsheng Li, Pan Peng.
In 24th International Symposium on Algorithms and Computation (ISAAC 2013). Arxiv version.
A Local Algorithm for Finding Dense Bipartite-Like Subgraphs.
Pan Peng.
In 18th Annual International Computing and Combinatorics Conference (COCOON 2012). DOI.
The Small Community Phenomenon in Networks: Models, Algorithms and Applications.
Pan Peng.
In 9th Annual Conference on Theory and Applications of Models of Computation (TAMC 2012). DOI.
The Small-Community Phenomenon in Networks.
Angsheng Li, Pan Peng.
Mathematical Structures in Computer Sciences 22, pp 373-407, 2012. Arxiv version.
Community Structures in Classical Network Models.
Angsheng Li, Pan Peng.
Internet Mathematics 7(2), 2011. DOI
Teaching:
Algorithms for Big Data. 2022 Spring.
Advanced Algorithms. 2018-2019, 2019-2020, 2020-2021.
Automata, Computation and Complexity. 2018-2019, 2019-2020, 2020-2021.
Contact Information:
Advanced Algorithms. 2018-2019, 2019-2020, 2020-2021.
Automata, Computation and Complexity. 2018-2019, 2019-2020, 2020-2021.
Contact Information:
Pan Peng
School of Computer Science and Technology
University of Science and Technology of China
School of Computer Science and Technology
University of Science and Technology of China