4 papers
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…
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…
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 and sufficiently large , we give an explicit constr…
Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty +2
We construct the first explicit two-sided vertex expanders that bypass the spectral barrier. Previously, the strongest known explicit vertex expanders were given by -regular Ram…