Home
Hello! I'm Jun-Ting Hsieh, and I go by the name "Tim". I am currently a C.L.E. Moore Instructor of Mathematics at MIT (departmental postdoc).
I am broadly interested in Theoretical Computer Science. Recently, I've been thinking about expander graphs and other pseudorandom objects, and their connections to algorithms beyond the worst case. More generally, my research interests (and prior work) include explicit constructions, coding theory, average-case complexity, semidefinite programming and the Sum-of-Squares hierarchy, and extremal combinatorics.
Before MIT, I completed my PhD in the Computer Science Department at Carnegie Mellon University, where I was fortunate to be advised by Pravesh K. Kothari. My PhD thesis can be found here.
Research Highlights
For my papers, see my publication list (selected, by year, or by topic).
Explicit constructions of expanders and pseudorandom objects
- We give the first explicit construction of constant-degree lossless vertex expanders (in the sequence [HMMP24, HLMOZ25, HLMRZ25]); see [HLW06] for the history and context of this problem. My blog post has an overview of the construction and the key ingredient - tripartite line product. See also my talk and Rachel's talk.
- We construct explicit ε-balanced codes [HMZ26] with rate and distance almost matching the GV bound. We give a simple construction using free expander walks; see more in this talk.
- We construct explicit constant-alphabet subspace design codes [GGH26] using the expander-based AEL framework. The subspace design property captures list-decoding, list-recovery, and proximity gaps (see Venkat's talk).
Algorithms beyond the worst case
- We develop efficient algorithms to partially color 3-colorable graphs when the input graph is an expander [BHK25] or has low threshold rank [H26]. See more in this talk.
- We give efficient algorithms to solve semirandom CSPs (hybrids between worst-case and average-case input models). We study both the refutation problem [HKM23] and the search problem [GHKM23].
- The techniques developed along the way led to improved lower bounds for locally decodable codes [BHKL25] and new results in extremal combinatorics [HKMMS25]. See my talk and Pravesh's talk on the Kikuchi method.
Average-case complexity and the low-degree heuristic
- We refute the low-degree conjecture of Hopkins (in the quasi-polynomial regime) [BHJK25]. This conjecture is the basis of the low-degree method, which is widely used to predict information-computation gaps in statistical signal detection and recovery problems (see the surveys [KWB19, W25]).
- We investigate what low-degree hardness can prove unconditionally [HKKLMT26]. We develop tools that turn low-degree hardness into unconditional lower bounds against concrete statistical tests and algorithms.