Next
Three-player number-on-forehead pointer chasing has communication complexity $\le n^{1-c}$. A bound $n/\log^{c}n$ was known since the 90's.
more >>>We present an explicit weight assignment generator that uses a seed of length $O(\log(wn))$ to assign a polynomially-bounded integer weight to each vertex of any simple width-$w$ length-$n$ layered digraph. For each such digraph, there is at least one seed such that the weight function is min-isolating, i.e., the minimum-weight ... more >>>
Zero-knowledge ($ZK$) protocols are one of the most fundamental cryptographic primitives. Classic results in the 1980s established that one-way functions (OWFs) suffice for constructing $ZK$ for $NP$ (Goldreich-Micali-Wigderson [JACM'91], Naor [CRYPTO’89], Hastad et al. [SICOMP’99]). Moreover, OWFs are, in fact, necessary for $ZK$ for $NP$, due to the classic result ... more >>>