Jun-Ting (Tim) Hsieh
C.L.E. Moore Instructor of Mathematics, MIT
juntingh [at] mit [dot] edu
Google scholar
C.L.E. Moore Instructor of Mathematics, MIT
juntingh [at] mit [dot] edu
Google scholar
I am a C.L.E. Moore Instructor of Mathematics at MIT (departmental postdoc)!
My official name is Jun-Ting Hsieh, but I go by the name "Tim". I completed my PhD in the Computer Science Department at Carnegie Mellon University, where I was fortunate to be advised by Pravesh K. Kothari. I am broadly interested in Theoretical Computer Science. Recently, I've been thinking about constructions of expanders and their applications in coding theory. More generally, my research interests (and prior work) include average-case algorithms, semidefinite programming and the Sum-of-Squares hierarchy, and connections between TCS and extremal combinatorics.
I had the privilege of visiting Luca Trevisan at Bocconi University in the summer of 2022, and visiting Venkatesan Guruswami and Prasad Raghavendra at Berkeley in the summer of 2023.
Sparsifying Cayley Graphs on Every Group
Jun-Ting Hsieh,
Daniel Z. Lee,
Sidhanth Mohanty,
Aaron Putterman,
Rachel Yun Zhang
arXiv, 2025
Coloring 3-Colorable Graphs with Low Threshold Rank
Jun-Ting Hsieh
arXiv, 2025
Solving Random Planted CSPs below the n^{k/2} Threshold
Arpon Basu,
Jun-Ting Hsieh,
Andrew D. Lin,
Peter Manohar
arXiv, 2025
Explicit Lossless Vertex Expanders
Jun-Ting Hsieh,
Alex Lubotzky,
Sidhanth Mohanty,
Assaf Reiner,
Rachel Yun Zhang
FOCS, 2025
Best Paper Award
[CMU blog]
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai,
Jun-Ting Hsieh,
Aayush Jain,
Pravesh K. Kothari
FOCS, 2025
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
Arpon Basu,
Jun-Ting Hsieh,
Pravesh K. Kothari,
Andrew D. Lin
FOCS, 2025
Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh,
Ting-Chun Lin,
Sidhanth Mohanty,
Ryan O'Donnell,
Rachel Yun Zhang
STOC, 2025
Invited to SICOMP Special Issue for STOC 2025
Rounding Large Independent Sets on Expanders
Mitali Bafna,
Jun-Ting Hsieh,
Pravesh K. Kothari
STOC, 2025
[Talk at IAS]
Predicting quantum channels over general product distributions
Sitan Chen,
Jaume de Dios Pont,
Jun-Ting Hsieh,
Hsin-Yuan Huang,
Jane Lange,
Jerry Li
COLT, 2025
Explicit two-sided unique-neighbor expanders
Jun-Ting Hsieh,
Theo McKenzie,
Sidhanth Mohanty,
Pedro Paredes
STOC, 2024
[Slides]
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
Jun-Ting Hsieh,
Pravesh K. Kothari,
Sidhanth Mohanty,
David Munhá Correia,
Benny Sudakov
International Mathematics Research Notices, 2025
New SDP Roundings and Certifiable Approximation for Cubic Optimization
Jun-Ting Hsieh,
Pravesh K. Kothari,
Lucas Pesenti,
Luca Trevisan
SODA, 2024
Ellipsoid Fitting Up to a Constant
Jun-Ting Hsieh,
Pravesh K. Kothari,
Aaron Potechin,
Jeff Xu
ICALP, 2023
[Slides]
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
Jun-Ting Hsieh,
Pravesh K. Kothari
ICALP, 2023
[Slides]
A simple and sharper proof of the hypergraph Moore bound
Jun-Ting Hsieh,
Pravesh K. Kothari,
Sidhanth Mohanty
SODA, 2023
[Slides]
[Luca Trevisan's blog post]
Polynomial-Time Power-Sum Decomposition of Polynomials
Mitali Bafna,
Jun-Ting Hsieh,
Pravesh K. Kothari,
Jeff Xu
FOCS, 2022
[Talk at CRM]
Certifying solution geometry in random CSPs: counts, clusters and balance
Jun-Ting Hsieh,
Sidhanth Mohanty,
Jeff Xu
CCC, 2022
Algorithmic Thresholds for Refuting Random Polynomial Systems
Jun-Ting Hsieh,
Pravesh K. Kothari
SODA, 2022
Learning Neural PDE Solvers with Convergence Guarantees
Jun-Ting Hsieh*,
Shengjia Zhao*,
Stephan Eismann,
Lucia Mirabella,
Stefano Ermon
ICLR, 2019
Learning to Decompose and Disentangle Representations for Video Prediction
Jun-Ting Hsieh,
Bingbin Liu,
De-An Huang,
Li Fei-Fei,
Juan Carlos Niebles
NeurIPS, 2018
Code
Graph Distillation for Action Detection with Privileged Modalities
Zelun Luo,
Jun-Ting Hsieh,
Lu Jiang,
Juan Carlos Niebles,
Li Fei-Fei
ECCV, 2018
Project
Code
Computer Vision-based Descriptive Analytics of Seniors' Daily Activities for Long-term Health Monitoring
Jun-Ting Hsieh*,
Zelun Luo*,
Niranjan Balachandar,
Serena Yeung,
Guido Pusiol,
Jay Luxenberg,
Grace Li,
Li-Jia Li,
N. Lance Downing,
Arnold Milstein,
Li Fei-Fei
Machine Learning for Healthcare (MLHC), 2018
Direct kinetic measurement of the reaction of the simplest Criegee intermediate with water vapor
Wen Chao,
Jun-Ting Hsieh,
Chun-Hung Chang,
Jim Jr-Min Lin
Science, 2015. Vol. 347, Issue 6223, pp. 751-754
Quantum Complexity Theory
TCS Toolkit Writing Project, 2020
Quantum Information Theory
Jun-Ting Hsieh,
Bingbin Liu
Course project, 2019