Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR22-163 | 16th November 2022
Gil Cohen, Gal Maor

Random Walks on Rotating Expanders

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

TR15-209 | 29th December 2015
Eli Ben-Sasson, Gal Maor

On the information leakage of public-output protocols

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

TR15-139 | 25th August 2015
Eli Ben-Sasson, Gal Maor

Lower bound for communication complexity with no public randomness

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

ISSN 1433-8092 | Imprint