10 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…
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…
Eigenvalue Bounds for Random Matrices via Zerofreeness
Sidhanth Mohanty, Amit Rajaraman
We introduce a new technique to prove bounds for the spectral radius of a random matrix, based on using Jensen's formula to establish the zerofreeness of the associated characteris…
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…
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra +2
Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to…
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…