16 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…
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…
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…
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…
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…
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…
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 , any -query binary, possibly non-linear locally decodable code (-LDC) must satisfy $k \leq \tilde{…
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…
Predicting quantum channels over general product distributions
Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh +3
We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an -qubit channel and an observable , we aim to learn the…
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the Dimension Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
We consider the task of certifying that a random -dimensional subspace in is well-spread - every vector satisfies $c\sqrt{n} \|x\|_2 \leq \|x\|_1 \l…
Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has…
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty +2
Given a -uniform hypergraph on vertices, an even cover in is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalizat…
New SDP Roundings and Certifiable Approximation for Cubic Optimization
Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti +1
We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the -dimensional hypercube. In both cases, the resulti…
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari +1
We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case an…