Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext next

TR21-084 | 21st June 2021
Liron Bronfman, Ron Rothblum

PCPs and Instance Compression from a Cryptographic Lens

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic ... more >>>

TR21-083 | 21st June 2021
Mark Braverman, Sumegha Garg, Or Zamir

Tight Space Complexity of the Coin Problem

In the coin problem we are asked to distinguish, with probability at least $2/3$, between $n$ $i.i.d.$ coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>

TR21-082 | 16th June 2021
Rahul Ilango, Hanlin Ren, Rahul Santhanam

Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>

Next next

ISSN 1433-8092 | Imprint