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
-
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 note on a hierarchy theorem for promise-BPTIME
Songhua He
AI-assisted works
-
Testing MAX-CUT in the Adjacency Matrix Model: Tight Non-Adaptive Bounds and a Cubic Adaptive Lower Bound
Songhua He
-
Should Tables Be Sorted? Revisited with a Large Language Model
Songhua He