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


TR26-049 | 7th April 2026
Mika Göös, Nathaniel Harms, Florian Richter, Anastasia Sofronova

No Constant-Cost Protocol for Point–Line Incidence

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point–Line Incidence problem is $\Theta(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, ... more >>>



Next next


ISSN 1433-8092 | Imprint