12 papers
Explicit Constant-Alphabet Subspace Design Codes
Rohan Goyal, Venkatesan Guruswami, Jun-Ting Hsieh
The subspace design property for additive codes is a higher-dimensional generalization of the minimum distance property. As shown recently by Brakensiek, Chen, Dhar and Zhang, it i…
Explicit Almost-Optimal -Balanced Codes via Free Expander Walks
Jun-Ting Hsieh, Sidhanth Mohanty, Rachel Yun Zhang
We study the problem of constructing explicit codes whose rate and distance match the Gilbert-Varshamov bound in the low-rate, high-distance regime. In 2017, Ta-Shma gave an explic…
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
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 cut (or spectral) sparsifier which prese…
Coloring 3-Colorable Graphs with Low Threshold Rank
Jun-Ting Hsieh
We present a new algorithm for finding large independent sets in -colorable graphs with small -sided threshold rank. Specifically, given an -vertex -colorable graph who…
Solving Random Planted CSPs below the Threshold
Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1
We present a family of algorithms to solve random planted instances of any -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…