All reports by Author Louis Golowich:

__
TR23-178
| 16th November 2023
__

Louis Golowich, Tali Kaufman#### NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

__
TR23-173
| 15th November 2023
__

Louis Golowich, Venkatesan Guruswami#### Quantum Locally Recoverable Codes

__
TR23-089
| 15th June 2023
__

Louis Golowich#### New Explicit Constant-Degree Lossless Expanders

Revisions: 1

__
TR23-065
| 4th May 2023
__

Louis Golowich#### From Grassmannian to Simplicial High-Dimensional Expanders

Revisions: 1

__
TR22-181
| 15th December 2022
__

Louis Golowich#### A New Berry-Esseen Theorem for Expander Walks

Revisions: 1

__
TR22-024
| 17th February 2022
__

Louis Golowich, Salil Vadhan#### Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

Revisions: 1

__
TR21-099
| 4th July 2021
__

Louis Golowich#### Improved Product-Based High-Dimensional Expanders

Louis Golowich, Tali Kaufman

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

Louis Golowich, Venkatesan Guruswami

Classical locally recoverable codes, which permit highly efficient recovery from localized errors as well as global recovery from larger errors, provide some of the most useful codes for distributed data storage in practice. In this paper, we initiate the study of quantum locally recoverable codes (qLRCs). In the long ... more >>>

Louis Golowich

We present a new explicit construction of onesided bipartite lossless expanders of constant degree, with arbitrary constant ratio between the sizes of the two vertex sets. Our construction is simpler to state and analyze than the prior construction of Capalbo, Reingold, Vadhan, and Wigderson (2002).

We construct our ... more >>>

Louis Golowich

In this paper, we present a new construction of simplicial complexes of subpolynomial degree with arbitrarily good local spectral expansion. Previously, the only known high-dimensional expanders (HDXs) with arbitrarily good expansion and less than polynomial degree were based on one of two constructions, namely Ramanujan complexes and coset complexes. ... more >>>

Louis Golowich

We prove that the sum of $t$ boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of $O(\lambda/t^{1/2-o(1)})$, where $\lambda$ is the second largest eigenvalue of the random walk matrix in absolute value. To ... more >>>

Louis Golowich, Salil Vadhan

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. We show that expander walks fool symmetric functions up to a $O(\lambda)$ error in ... more >>>

Louis Golowich

High-dimensional expanders generalize the notion of expander graphs to higher-dimensional simplicial complexes. In contrast to expander graphs, only a handful of high-dimensional expander constructions have been proposed, and no elementary combinatorial construction with near-optimal expansion is known. In this paper, we introduce an improved combinatorial high-dimensional expander construction, by modifying ... more >>>