Dr Pan Peng
Department of Computer Science
Full contact details
Department of Computer Science
Dr. Pan Peng joined the University of Sheffield as a Lecturer in Algorithms in April 2018. He has held postdoc positions at the University of Vienna, Austria, as well as the Technical University of Dortmund, Germany, from September 2013 to March 2018.
Before that, he obtained his PhD degree in Computer Science from Institute of Software, Chinese Academy of Sciences in 2013 and his Bachelor degree in Mathematics from Beijing Normal University, China in 2007.
- Research interests
Dr. Pan Peng's research interests lie on the intersection between theoretical computer science and network science, with the goal of developing new techniques to efficiently process and analyze diverse, dynamic and massive network data.
Currently, he is focused on very resource-efficient algorithms that read or store only a small portion of the large input while still have good and provable performance guarantees, including property testing, streaming algorithms.
He is also very interested in the theory and applications of dynamic graph algorithms, spectral graph theory, sparsification and random graphs.
- Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem. Algorithmica, 83, 3148-3179. View this article in WRRO
- Mixed-order spectral clustering for complex networks. Pattern Recognition. View this article in WRRO
- Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics (SIDMA), 34(1), 130-162. View this article in WRRO
- Dynamic Graph Stream Algorithms in o(n) Space. Algorithmica, 81(5), 1965-1987. View this article in WRRO
- Spectral concentration and greedy k-clustering. Computational Geometry -Theory and Applications, 76, 19-32. View this article in WRRO
- Equilibrium games in networks. Physica A: Statistical Mechanics and its Applications, 416, 49-60.
- Global core, and galaxy structure of networks. Science China Information Sciences, 57(7), 1-20.
- The small-community phenomenon in networks. Mathematical Structures in Computer Science, 22(3), 373-407.
- Community Structures in Classical Network Models. Internet Mathematics, 7(2), 81-106.
- Constant-Time Dynamic $(Δ+1)$-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing.
- Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.
Conference proceedings papers
- Sampling arbitrary subgraphs exactly uniformly in sublinear time. The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), Vol. 168 (pp 45:1-45:13). Saarbrücken, Germany, 8 July 2020 - 11 July 2020. View this article in WRRO
- Constant-time dynamic (∆ + 1)-coloring. The 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Vol. 154 (pp 53:1-53:18). Montpellier, France, 10 March 2020 - 13 March 2020. View this article in WRRO
- Robust clustering oracle and local reconstructor of cluster structure of graphs. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). Salt Lake City, Utah, USA, 5 January 2020 - 8 January 2020. View this article in WRRO
- More effective randomized search heuristics for graph coloring through dynamic optimization. Proceedings of the 2020 Genetic and Evolutionary Computation Conference View this article in WRRO
- Runtime analysis of randomized search heuristics for dynamic graph coloring. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 19). Prague, Czech Republic, 13 July 2019 - 17 July 2019. View this article in WRRO
- Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty. Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA19), 6 January 2019 - 9 January 2019. View this article in WRRO
- Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.. Proceedings of the 26th European Symposium on Algorithms (ESA 2018), Vol. 112, 20 August 2018 - 22 August 2018. View this article in WRRO
- Estimating Graph Parameters from Random Order Streams. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp 2449-2466)
- Improved guarantees for Vertex Sparsification in planar graphs. 25th Annual European Symposium on Algorithms (ESA 2017), Vol. 87 (pp 44:1-44:14). Vienna, Austria, 4 September 2017 - 8 September 2017. View this article in WRRO
- The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms (ESA 2017), Vol. 87 (pp 45:1-45:14). Vienna, Austria, 4 September 2017 - 8 September 2017. View this article in WRRO
- Testable bounded degree graph properties are random order streamable. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Vol. 80 (pp 131:1-131:14). Dagstuhl, Germany, 10 July 2017 - 14 July 2017. View this article in WRRO
- Relating two property testing models for bounded degree directed graphs. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (pp 1033-1045)
- Dynamic Graph Stream Algorithms in o(n) Space. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy (pp 18:1-18:16)
- Testing Cluster Structure of Graphs. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (pp 723-732)
- On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA (pp 786-799)
- Testing Small Set Expansion in General Graphs. 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany (pp 622-635)
- Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure (pp 655-665)
- A Local Algorithm for Finding Dense Bipartite-Like Subgraphs (pp 145-156)
- The Small Community Phenomenon in Networks: Models, Algorithms and Applications (pp 40-49)
- View this article in WRRO Average Sensitivity of Spectral Clustering. The 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2020)
- View this article in WRRO Augmenting the Algebraic Connectivity of Graphs. In Proceedings of the 28th European Symposium on Algorithms (ESA 2020)
- View this article in WRRO Testable Properties in General Graphs and Random Order Streaming. In the 24th International Conference on Randomization and Computation (RANDOM 2020)
- On Testability of First-Order Properties in Bounded-Degree Graphs. The 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
- GSF-locality is not sufficient for proximity-oblivious testing. The Computational Complexity Conference (CCC 2021)
- Local Algorithms for Estimating Effective Resistance. The 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2021)
- Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle. In the 34th Annual Conference on Learning Theory (COLT 2021)
- Professional activities
Member of the Algorithms research group