Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with spectral expanders:
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 >>>

TR23-183 | 24th November 2023
Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled

Derandomized Squaring: An Analytical Insight into Its True Behavior

The notion of the derandomized square of two graphs, denoted as $G \circ H$, was introduced by Rozenman and Vadhan as they rederived Reingold's Theorem, $\mathbf{SL} = \mathbf{L}$. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and ... more >>>

ISSN 1433-8092 | Imprint