Jun-Ting Hsieh

activity

20232026

collaborators

Showing 2025Show all

5 papers · 1 filter

cs.DS2025

Sparsifying Cayley Graphs on Every Group

Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty +2

A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a $(1 \pm ε)$ cut (or spectral) sparsifier which prese…

cs.DS2025

Coloring 3-Colorable Graphs with Low Threshold Rank

Jun-Ting Hsieh

We present a new algorithm for finding large independent sets in $3$ -colorable graphs with small $1$ -sided threshold rank. Specifically, given an $n$ -vertex $3$ -colorable graph who…

cs.DS2025

Solving Random Planted CSPs below the $n^{k /2}$ Threshold

Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1

We present a family of algorithms to solve random planted instances of any $k$ -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…

cs.CC2025

The Quasi-Polynomial Low-Degree Conjecture is False

Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain +1

There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closene…

math.CO2025

Explicit Lossless Vertex Expanders

Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty +2

We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any $ε > 0$ and sufficiently large $d$ , we give an explicit constr…

Sparsifying Cayley Graphs on Every Group

Coloring 3-Colorable Graphs with Low Threshold Rank

Solving Random Planted CSPs below the nk/2 Threshold

The Quasi-Polynomial Low-Degree Conjecture is False

Explicit Lossless Vertex Expanders

Solving Random Planted CSPs below the $n^{k /2}$ Threshold