We study the randomized communication complexity of the equality function in the public-coin model. Although the communication complexity of this function is known to be low in the setting where error probability is constant and a large number of random bits are available to players, the complexity grows if the ... more >>>

In this work, we combine the work of Chen et. al and Hoza to obtain a WPRG against regular ROBPs
with seed length $O(\log t \cdot (\log w+\sqrt{\log \frac{1}{\epsilon}}+\log\log t) + \log \frac {1}{\epsilon})$, improving
upon previous construction which also include some additional lower order terms.

more >>>

We present an optimal ``worst-case exact to average-case approximate'' reduction for matrix multiplication over a finite field of prime order $p$. Any efficient algorithm that correctly computes, in expectation, at least $(\frac{1}{p} + \varepsilon)$-fraction of entries of the multiplication $A \cdot B$ of a pair $(A, B)$ of uniformly ... more >>>