In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in an ... more >>>

We study the black-box function inversion problem, which is the problem of finding $x \in [N]$ such that $f(x) = y$, given as input some challenge point $y$ in the image of a function $f : [N] \to [N]$, using $T$ oracle queries to $f$ and preprocessed advice $\sigma \in ... more >>>

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms.

... more >>>