Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR23-173 | 15th November 2023
Louis Golowich, Venkatesan Guruswami

Quantum Locally Recoverable Codes

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 >>>

TR23-089 | 15th June 2023
Louis Golowich

New Explicit Constant-Degree Lossless Expanders

Revisions: 1

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 >>>

TR23-065 | 4th May 2023
Louis Golowich

From Grassmannian to Simplicial High-Dimensional Expanders

Revisions: 1

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 >>>

TR22-181 | 15th December 2022
Louis Golowich

A New Berry-Esseen Theorem for Expander Walks

Revisions: 1

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 >>>

TR22-024 | 17th February 2022
Louis Golowich, Salil Vadhan

Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

Revisions: 1

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 >>>

TR21-099 | 4th July 2021
Louis Golowich

Improved Product-Based High-Dimensional Expanders

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 >>>

ISSN 1433-8092 | Imprint