Songhua He
PhD Student in Theoretical Computer Science
Rutgers University
songhuahe.cs@gmail.com
I am a PhD student at Rutgers University, advised by Periklis A. Papakonstantinou and Sumegha Garg.
I obtained my Bachelor's degree from the School of Electronics Engineering and Computer Science, Peking University.
My research lies within computational complexity and information theory, with a specific focus on property testing and the limits of computational models.
I'm broadly interested in the theory of computing.
Publications
* Note: In Theoretical Computer Science, authors are listed alphabetically.
-
Data Structure Lower Bounds via the Query-with-Sketch Model
with Sumegha Garg, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang
CCC 2026
[to appear]
-
Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds
with Chengyuan Deng, Jie Gao, Chen Wang
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
with Sumegha Garg, Periklis A. Papakonstantinou
-
The Effect of Weight Precision on the Neuron Count in Deep ReLU Networks
with Periklis A. Papakonstantinou
Manuscripts
-
A lower bound for testing the max cut size in dense graphs
Songhua He
[in preparation]
-
A note on a hierarchy theorem for promise-BPTIME
Songhua He