I am a postdoctoral scholar at University of Washington, working with Rachel Lin and Jamie Morgenstern. I obtained my PhD from the Courant Institute of Mathematical Sciences at New York University under the supervision of Joan Bruna and Oded Regev.

I am on the 2024–2025 academic job market! Please feel free to reach out to me at mjsong32@cs.washington.edu.

Research interests

I am interested in theoretical computer science and the foundations of machine learning. I use computational hardness as a tool to uncover fundamental limitations and guide adversarial thinking in machine learning. More broadly, I explore emerging problems from machine learning and high-dimensional statistics through the computational lens.

News

• 2024/09: My paper Cryptographic Hardness of Score Estimation has been accepted for publication at NeurIPS2024. Gaussian pancakes strike again!
• 2024/02: I gave a talk on the computational complexity of statistical inference at the Korea University Statistics Seminar.
• 2023/05: I obtained my PhD! I will be starting as a postdoctoral scholar at University of Washington.
• 2023/03: A nice ML security application of Continuous LWE and Gaussian pancakes has been featured in the Quanta article, In Neural Networks, Unbreakable Locks Can Hide Invisible Doors.

Publications

(α-β) denotes alphabetical ordering, * denotes equal contribution.

Cryptographic Hardness of Score Estimation. Min Jae Song. Advances in Neural Information Processing System (NeurIPS), 2024. [arxiv]

Learning Single-Index Models with Shallow Neural Networks. Alberto Bietti, Joan Bruna, Clayton Sanford, Min Jae Song (α-β). Advances in Neural Information Processing Systems (NeurIPS), 2022. [arxiv]

Lattice-Based Methods Surpass Sum-of-Squares in Clustering. Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna. Proceedings of the Conference on Learning Theory (COLT), 2022. [arxiv, video]

On the Cryptographic Hardness of Learning Single Periodic Neurons. Min Jae Song*, Ilias Zadik*, Joan Bruna. Advances in Neural Information Processing Systems (NeurIPS), 2021. [arxiv, video]

Continuous LWE. Joan Bruna, Oded Regev, Min Jae Song, Yi Tang (α-β). ACM Symposium on Theory of Computing (STOC), 2021. [arxiv, video]

Self-Supervised Motion Retargeting with Safety Guarantee. Sungjoon Choi, Min Jae Song, Hyemin Ahn, Joohyung Kim. IEEE International Conference on Robotics and Automation (ICRA), 2021. [arxiv, video]

Evaluating Representations by the Complexity of Learning Low-Loss Predictors. William F. Whitney, Min Jae Song, David Brandfonbrener, Jaan Altosaar, Kyunghyun Cho. ICLR Neural Compression Workshop, 2021. [arxiv, code, blog]

Hardness of Approximate Nearest Neighbor Search under L-Infinity. Young Kun Ko, Min Jae Song (α-β). arXiv preprint, 2020. [arxiv]