Author name cluster

Ting-Chun Lin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

STOC Conference 2025 Conference Paper

Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier

Jun-Ting Hsieh
Ting-Chun Lin
Sidhanth Mohanty
Ryan O'Donnell
Rachel Yun Zhang

We construct the first explicit two-sided vertex expanders that bypass the spectral barrier. Previously, the strongest known explicit vertex expanders were given by d -regular Ramanujan graphs, whose spectral properties imply that every small subset of vertices S has at least 0.5 d | S | distinct neighbors. However, it is possible to construct Ramanujan graphs containing a small set S with no more than 0.5 d | S | neighbors. In fact, no explicit construction was known to break the 0.5 d -barrier. In this work, we give an explicit construction of an infinite family of d -regular graphs (for large enough d ) where every small set expands by a factor of ≈ 0.6 d . More generally, for large enough d 1 , d 2 , we give an infinite family of ( d 1 , d 2 )-biregular graphs where small sets on the left expand by a factor of ≈ 0.6 d 1 , and small sets on the right expand by a factor of ≈ 0.6 d 2 . In fact, our construction satisfies an even stronger property: small sets on the left and right have unique-neighbor expansion 0.6 d 1 and 0.6 d 2 respectively. Our construction follows the tripartite line product framework of Hsieh et. al., and instantiates it using the face-vertex incidence of the 4-dimensional Ramanujan clique complex as its base component. As a key part of our analysis, we derive new bounds on the triangle density of small sets in the Ramanujan clique complex.

Details

STOC Conference 2025 Conference Paper

Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes

Louis Golowich
Ting-Chun Lin

For every integer r ≥ 2 and every є>0, we construct an explicit infinite family of quantum LDPC codes supporting a transversal C r −1 Z gate with length N , dimension K ≥ N 1−є , distance D ≥ N 1/ r / poly (log N ), and stabilizer weight w ≤ poly (log N ). The previous state of the art construction (in most parameter regimes) was the r -dimensional color code, which has only constant dimension K = O (1), and otherwise has the same parameters up to polylogarithmic factors. Our construction provides the first known codes with low-weight stabilizers that are capable of magic state distillation with arbitrarily small yield parameter γ=log( N / K )/log( D )>0. A classical analogue of transversal C r −1 Z gates is given by the multiplication property, which requires component-wise products of classical codewords to belong to another similar code. As a byproduct of our techniques, we also obtain a new construction of classical locally testable codes with such a multiplication property. We construct our codes as products of chain complexes associated to classical LDPC codes, which in turn we obtain by imposing local Reed-Solomon codes on a specific spectral expander that we construct. We prove that our codes support the desired transversal C r −1 Z gates by using the multiplication property to combine local circuits based on the topological structure.

Details

FOCS Conference 2024 Conference Paper

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

Irit Dinur
Ting-Chun Lin
Thomas Vidick

We introduce a high-dimensional cubical complex, for any dimension $t \in \mathbb{N}$, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case $t=2$ ), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes $h_{1}, \ldots, h_{t}$ as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For $t=4$ our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.

Details

STOC Conference 2023 Conference Paper

Good Quantum LDPC Codes with Linear Time Decoders

Irit Dinur
Min-Hsiu Hsieh
Ting-Chun Lin
Thomas Vidick

We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (2 m × m ) V → δ 0 (2 m ) E → δ 1 2 F where V ( X -checks) are the vertices, E (qubits) are the edges, and F ( Z -checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes C A , C B :2 m →2 Δ where Δ is the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

Details

FOCS Conference 2022 Conference Paper

Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares

Max Hopkins
Ting-Chun Lin

We construct an explicit family of 3-XOR instances hard for $\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness of random instances up to imperfect completeness (Grigoriev TCS 2001, Schoenebeck FOCS 2008). Our result is based on a new form of small-set high dimensional expansion (SS-HDX) inspired by recent breakthroughs in locally testable and quantum LDPC codes. Adapting the recent framework of Dinur, Filmus, Harsha, and Tulsiani (ITCS 2021) for SoS lower bounds from the Ramanujan complex to this setting, we show any (bounded-degree) SS-HDX can be transformed into a highly unsatisfiable 3-XOR instance that cannot be refuted by $\Omega(n)$-levels of SoS. We then show Leverrier and Zémor’s (Arxiv 2022) recent qLDPC construction gives the desired explicit family of bounded-degree SS-HDX. Incidentally, this gives the strongest known form of bi-directional high dimensional expansion to date. A full version of this paper is accessible at: https: //arxiv. org/abs/2204. 11469.

Details