Jun-Ting Hsieh

activity

20232026

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2026

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…

cs.CC2026

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…

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…

cs.CC2024

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1

We prove that for every odd $q \geq 3$ , any $q$ -query binary, possibly non-linear locally decodable code ( $q$ -LDC) $E : {\pm 1}^{k} \to {\pm 1}^{n}$ must satisfy $k \leq \tilde{…

Rigorous Implications of the Low-Degree Heuristic

Explicit Almost-Optimal ε-Balanced Codes via Free Expander Walks

The Quasi-Polynomial Low-Degree Conjecture is False

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Explicit Almost-Optimal $ε$ -Balanced Codes via Free Expander Walks