Submissions claiming to resolve a grand challenge, such as the P vs. NP problem, may be rejected without further consideration.
Submissions containing an essential part that seems to be generated by AI tools and/or are written in a way that humans will find hard to understand, may be rejected regardless of their merits. ECCC is intended for communication among humans.
For more details see the Call for Papers.In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.
It seems that this blocking was just removed, and we hope it will not be put back in the future.
Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.
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 >>>
Suppose an untrusted powerful data analyst collected many samples from an unknown distribution, and claims that the distribution satisfies some property. For example, that it is close to uniform, or has large support. Can they provide a convincing proof to this effect? If so, what is the complexity of certifying ... more >>>