Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR26-324 | 20th November 2026
Emanuele Viola

A power saving for pointer chasing

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

TR26-323 | 20th November 2026
William Hoza

NL = UL

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


TR26-322 | 19th November 2026
Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak

Complexity-Theoretic Consequences of Zero-Knowledge with Inefficient Simulation

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



Next next


ISSN 1433-8092 | Imprint