Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DERANDOMIZED SQUARING:
Reports tagged with derandomized squaring:
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