We prove that for every $\alpha \in [1,1.5]$,
$$
\text{BPSPACE}[S]\subseteq \text{TISP}[2^{S^{\alpha}},S^{3-\alpha}]
$$
where $\text{BPSPACE}[S]$ corresponds to randomized space $O(S)$ computation, and $\text{TISP}[T,S]$ to time $poly(T)$, space $O(S)$ computation. Our result smoothly interpolates between the results of (Nisan STOC 1992) and (Saks and Zhou FOCS 1995), which prove $\text{BPSPACE}[S]$ is contained ... more >>>

We give an explicit construction of non-malleable codes with rate $1-o(1)$ for the tampering class of poly-size circuits. This rate is optimal, and improves upon the previous explicit construction of Ball, Dachman-Soled and Loss (CRYPTO 2022) which achieves a rate smaller than $\frac{1}{n}$. Our codes are based on the same ... more >>>

We define and study the model of patterned non-determinism in bipartite communication complexity, denoted by $PNP^{X\leftrightarrow Y}$.
It generalises the known models $UP^{X\leftrightarrow Y}$ and $FewP^{X\leftrightarrow Y}$ through relaxing the constraints on the witnessing structure of the underlying $NP^{X\leftrightarrow Y}$-protocol.
It is shown that for the case of total functions ... more >>>