Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with unique neighbor expanders:
TR23-090 | 15th June 2023
Itay Cohen, Roy Roth, Amnon Ta-Shma

HDX Condensers

More than twenty years ago, Capalbo, Reingold, Vadhan and Wigderson gave the first (and up to date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas together with extractor technology, and is rather complicated. We give an alternative construction that builds upon ... more >>>

TR23-110 | 25th July 2023
Gil Cohen, Tal Yankovitz

Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries

Revisions: 1

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With ... more >>>

TR23-160 | 29th October 2023
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes

Revisions: 1

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

ISSN 1433-8092 | Imprint