Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-160 | 26th January 2024 09:06

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

RSS-Feed




Revision #1
Authors: Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
Accepted on: 26th January 2024 09:06
Downloads: 106
Keywords: 


Abstract:

In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by
Sipser-Spielman [SS96] (and Tanner [Tan81]), and their analysis. We also show how to obtain expanders with many unique neighbors using similar ideas.

There were many exciting results on this topic recently, starting with Asherov-Dinur [AD23] and Hsieh-McKenzie-Mohanty-Paredes [HMMP23], who gave a similar construction of unique neighbor expander graphs, but using more sophisticated ingredients (such as almost-Ramanujan graphs) and a more involved analysis. Subsequent beautiful works of Cohen-Roth-TaShma [CRT23] and Golowich [Gol23] gave even stronger objects (lossless expanders), but also using sophisticated ingredients.

The main contribution of this work is that we get much more elementary constructions of unique neighbor expanders and with a simpler analysis.


Paper:

TR23-160 | 29th October 2023 10:46

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes


Abstract:

In this note, we give very simple constructions of unique neighbor expander graphs starting from spectral or combinatorial expander graphs of mild expansion. These constructions and their analysis are simple variants of the constructions of LDPC error-correcting codes from expanders, given by
Sipser-Spielman~\cite{SS96} (and Tanner~\cite{Tanner81}), and their analysis. We also show how to obtain expanders with many unique neighbors using similar ideas.

There were many exciting results on this topic recently, starting with Asherov-Dinur~\cite{AD23} and Hsieh-McKenzie-Mohanty-Paredes~\cite{HMMP23}, who gave a similar construction of unique neighbor expander graphs, but using more sophisticated ingredients (such as almost-Ramanujan graphs) and a more involved analysis. Subsequent beautiful works of Cohen-Roth-TaShma~\cite{CRT23} and Golowich~\cite{Golowich23} gave even stronger objects (lossless expanders), but also using sophisticated ingredients.

The main contribution of this work is that we get much more elementary constructions of unique neighbor expanders and with a simpler analysis.



ISSN 1433-8092 | Imprint