Showing 2026Show all
3 papers · 1 filter
cs.IT2026
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…
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…