All reports by Author Itay Cohen:

__
TR23-183
| 24th November 2023
__

Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled#### Derandomized Squaring: An Analytical Insight into Its True Behavior

__
TR23-090
| 15th June 2023
__

Itay Cohen, Roy Roth, Amnon Ta-Shma#### HDX Condensers

__
TR22-154
| 6th November 2022
__

Gil Cohen, Itay Cohen#### Spectral Expanding Expanders

Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled

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

Itay Cohen, Roy Roth, Amnon Ta-Shma

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

Gil Cohen, Itay Cohen

Dinitz, Schapira, and Valadarsky (Algorithmica 2017) introduced the intriguing notion of expanding expanders -- a family of expander graphs with the property that every two consecutive graphs in the family differ only on a small number of edges. Such a family allows one to add and remove vertices with only ... more >>>