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-052 | 7th April 2026
Shuichi Hirahara, Mikito Nanashima

A Sharp Characterization of Pessiland

It is a long-standing open question whether the average-case hardness of NP implies the existence of a one-way function. The hypothetical world in which this does not hold is called Pessiland, which is the most pessimistic among Impagliazzo's five possible worlds. In this paper, we present the first "sharp" characterization ... more >>>


TR26-051 | 6th April 2026
Yanyi Liu, Noam Mazor, Rafael Pass

Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ?s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin ... more >>>


TR26-050 | 7th April 2026
Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak

Witness-Indistinguishable Arguments of Knowledge and One-Way Functions

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable ($WI$) arguments of knowledge. We establish that:

- Assuming that $NP\not\subseteq P/poly,$ the existence of a constant-round computational $WI$ argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist.

- Assuming that $NP\not\subseteq P^{Sam}/poly,$ there is no ... more >>>



Next next


ISSN 1433-8092 | Imprint