Songhua He

PhD Student in Theoretical Computer Science
Rutgers University

sh1511@scarletmail.rutgers.edu

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

Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds
with Chengyuan Deng, Jie Gao, Chen Wang

ICLR 2026 [to appear]
Query Lower Bounds for Correlation Clustering under Memory Constraints
with Sumegha Garg, Periklis A. Papakonstantinou

ITCS 2026 [to appear]
The Effect of Weight Precision on the Neuron Count in Deep ReLU Networks
with Periklis A. Papakonstantinou

ICML 2024 [ICML, ECCC]

Manuscripts

* Note: In Theoretical Computer Science, authors are listed alphabetically.

A lower bound for testing the max cut size in dense graphs
Songhua He

[under submission]
Data Structure Lower Bounds via the Query-with-Sketch Model
with Sumegha Garg, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang

[under submission]
A note on a hierarchy theorem for promise-BPTIME
Songhua He

2025 [ECCC, Oded's Choices]