I am a DSI postdoctoral scholar at the University of Chicago, mentored by Aloni Cohen. Prior to this, I was a postdoctoral scholar at the 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.

Please feel free to reach out at minjae.song äţ uchicago.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]