Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-096 | 16th July 2025
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

Searching for Falsified Clause in Random $(\log{n})$-CNFs is Hard for Randomized Communication

We show that for a randomly sampled unsatisfiable $O(\log n)$-CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in $n$.

more >>>

TR25-095 | 15th July 2025
Rahul Ilango

Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and ... more >>>


TR25-094 | 14th July 2025
Shuichi Hirahara, Rahul Ilango, Bruno Loff

Communication Complexity is NP-hard

In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint