All reports by Author Gal Maor:

__
TR23-183
| 24th November 2023
__

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

__
TR22-163
| 16th November 2022
__

Gil Cohen, Gal Maor#### Random Walks on Rotating Expanders

__
TR15-209
| 29th December 2015
__

Eli Ben-Sasson, Gal Maor#### On the information leakage of public-output protocols

__
TR15-139
| 25th August 2015
__

Eli Ben-Sasson, Gal Maor#### Lower bound for communication complexity with no public randomness

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

Gil Cohen, Gal Maor

Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -- the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As ... more >>>

Eli Ben-Sasson, Gal Maor

In this paper three complexity measures are studied: (i) internal information, (ii) external information, and (iii) a measure called here "output information". Internal information (i) measures the counter-party privacy-loss inherent in a communication protocol. Similarly, the output information (iii) measures the reduction in input-privacy that is inherent when the output ... more >>>

Eli Ben-Sasson, Gal Maor

We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was first stated in Yao's seminal paper [STOC 1979], but no full proof appears in the literature.

Our proof ... more >>>